Matrix

• 1. Prerequisites
• 2. Matrix
• 3. Matrix Addition
• 4. Scalar Multiplication
• 5. Matrix Multiplication
  • 5.1. Properties of Matrix Multiplication
    • 5.1.1. Associativity
    • 5.1.2. Distributivity
    • 5.1.3. Square Matrix
• 6. Block Matrix Multiplication
• 7. Matrix as a Linear Map
• 8. Transpose
• 9. Orthogonal matrix
• 10. Conjugate
• 11. Hermitian
• 12. Trace
• 13. Inner Product
  • 13.1. 向量的标准内积
  • 13.2. 矩阵的 Frobenius 内积
• 14. Determinant
  • 14.1. Alternating multilinear map
  • 14.2. Laplace expansion
• 15. Adjugate matrix

1. Prerequisites

• 向量空间
• 群论(置换群)

Let $F$ be a field(e.g. $F=\mathbb{Q},F=\mathbb{R}$ or $F=\mathbb{C}$)

$0_F$ is the addtive unit element of $F$.

$1_F$ is the multiply unit element of $F$.

We will use $0$ and $1$ to denote $0_F$ and $1_F$ respectively if there is no confusion about the field $F$.

2. Matrix

A matrix is a rectangular array of elements from a field $F$.

$$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]$$

The element $a_{ij}$ is called the $(i,j)$-th entry of $A$.

$F^{m\times n}$ is the set of all $m\times n$ matrices with entries in $F$.

3. Matrix Addition

Let $A=[a_{ij}]$ and $B=[b_{ij}]$ be two matrices of the same size. The sum of $A$ and $B$ is the matrix $C=[c_{ij}]$ defined by $c_{ij}=a_{ij}+b_{ij}$.

It is easy to see that $⟨F^{m\times n},+⟩$ is an commutative group.

4. Scalar Multiplication

Let $A=[a_{ij}]$ be a matrix and $c\in F$ be a scalar. The product of $A$ and $c$ is the matrix $C=[c_{ij}]$ defined by $c_{ij}=c{a}_{ij}$.

It is easy to see that $⟨F^{m\times n},+,\cdot ⟩$ is a vector space over $F$.

5. Matrix Multiplication

Let $A=[a_{ij}]\in F^{m\times n}$ and $B=[b_{ij}]\in F^{n\times p}$ be two matrices. The product of $A$ and $B$ is the matrix $C=[c_{ij}]\in F^{m\times p}$ defined by $c_{ij}={\sum }_{k=1}^n{a}_{ik}{b}_{kj}$.

5.1. Properties of Matrix Multiplication

5.1.1. Associativity

Let $A=[a_{ij}]\in F^{m\times n}$, $B=[b_{ij}]\in F^{n\times p}$, $C=[c_{ij}]\in F^{p\times q}$ be three matrices.

$$(AB)C=A(BC)$$

proof

$$\begin{array}{rl}((AB)C{)}_{ij}& =\sum _{k=1}^p(AB{)}_{ik}{c}_{kj}\\ & =\sum _{k=1}^p(\sum _{l=1}^n{a}_{il}{b}_{lk})c_{kj}\\ & =\sum _{k=1}^p\sum _{l=1}^n{a}_{il}{b}_{lk}{c}_{kj}\end{array}$$ $$\begin{array}{rl}A(BC{)}_{ij}& =\sum _{l=1}^n{a}_{il}(BC{)}_{lj}\\ & =\sum _{l=1}^n{a}_{il}\sum _{k=1}^p{b}_{lk}{c}_{kj}\\ & =\sum _{l=1}^n\sum _{k=1}^p{a}_{il}{b}_{lk}{c}_{kj}\\ & =\sum _{k=1}^p\sum _{l=1}^n{a}_{il}{b}_{lk}{c}_{kj}\\ & =((AB)C{)}_{ij}\end{array}$$

5.1.2. Distributivity

$$A(B+C)=AB+AC$$

proof

$$\begin{array}{rl}(A(B+C){)}_{ij}& =\sum _{k=1}^n{a}_{ik}(B+C{)}_{kj}\\ & =\sum _{k=1}^n{a}_{ik}(b_{kj}+c_{kj})\\ & =\sum _{k=1}^n{a}_{ik}{b}_{kj}+\sum _{k=1}^n{a}_{ik}{c}_{kj}\\ & =(AB{)}_{ij}+(AC{)}_{ij}\\ & =(AB+AC{)}_{ij}\end{array}$$

5.1.3. Square Matrix

A matrix $A$ is called a square matrix if $m=n$.

Identity Matrix

The $n\times n$ identity matrix $I_n$ is the matrix with $1_F$ on the diagonal and $0_F$ elsewhere.

$$I_n=\left[\begin{array}{cccc}{1}_F& 0_F& \cdots & 0_F\\ 0_F& 1_F& \cdots & 0_F\\ ⋮& ⋮& \ddots & ⋮\\ 0_F& 0_F& \cdots & 1_F\end{array}\right]$$

$I$ is the identity element of $⟨F^{n\times n},\cdot ⟩$.

$$AI=IA=A$$

proof

$$\begin{array}{rl}(AI{)}_{ij}& =\sum _{k=1}^n{a}_{ik}(I{)}_{kj}\\ & =\sum _{k=1}^n{a}_{ik}{\delta }_{kj}\\ & =a_{ij}\end{array}$$

similar, we have $IA=A$.

$⟨F^{n\times n},+,\cdot ⟩$ is a ring with identity.

because all the units in a ring form a group under multiplication(this group is called the group of units of the ring), the group of units of $⟨F^{n\times n},+,\cdot ⟩$ is denoted by $⟨\mathrm{GL}(n,F),\cdot ⟩$ or $\mathrm{GL}(n,F)$ or ${\mathrm{GL}}_n(F)$.

$\mathrm{GL}(n,F)$ is called the general linear group of degree $n$ over $F$.

6. Block Matrix Multiplication

let $A$ be a $m\times n$ matrix, $B$ be a $n\times p$ matrix, divide $A$ and $B$ into blocks:

$$A=\left[\begin{array}{cccc}{A}_{11}& A_{12}& \cdots & A_{1s}\\ A_{21}& A_{22}& \cdots & A_{2s}\\ ⋮& ⋮& \ddots & ⋮\\ A_{r1}& A_{r2}& \cdots & A_{rs}\end{array}\right],B=\left[\begin{array}{cccc}{B}_{11}& B_{12}& \cdots & B_{1t}\\ B_{21}& B_{22}& \cdots & B_{2t}\\ ⋮& ⋮& \ddots & ⋮\\ B_{s1}& B_{s2}& \cdots & B_{st}\end{array}\right]$$

where $A_{ij}$ is a $m_i\times n_j$ matrix, $B_{jk}$ is a $n_j\times p_k$ matrix, and satisfies:

• ${\sum }_{i=1}^r{m}_i=m$
• ${\sum }_{j=1}^s{n}_j=n$
• ${\sum }_{k=1}^t{p}_k=p$

then $C=AB$ can be represented as:

$$C=\left[\begin{array}{cccc}{C}_{11}& C_{12}& \cdots & C_{1t}\\ C_{21}& C_{22}& \cdots & C_{2t}\\ ⋮& ⋮& \ddots & ⋮\\ C_{r1}& C_{r2}& \cdots & C_{rt}\end{array}\right]$$

where $C_{ik}={\sum }_{j=1}^s{A}_{ij}{B}_{jk}$, and $C_{ik}$ is a $m_i\times p_k$ matrix.

7. Matrix as a Linear Map

设

$$A=[v_1\cdots v_n]\in F^{m\times n},v_i\in F^m.$$

对任意 $x=(x_1,\dots ,x_n{)}^T\in F^n$，矩阵乘法可以写成

$$Ax=\sum _{i=1}^n{x}_i{v}_i.$$

对任意 $x,y\in F^n$ 和 $a,b\in F$，矩阵乘法的分配律与数乘结合律给出

$$A(ax+by)=aAx+bAy.$$

因此矩阵 $A$ 定义了线性映射

$$T_A:F^n\to F^m,T_A(x)=Ax.$$

8. Transpose

Let $A=[a_{ij}]\in F^{m\times n}$ be a matrix. The transpose of $A$ is the matrix $A^T=[a_{ji}]\in F^{n\times m}$ defined by $a_{ji}=a_{ij}$.

$A\in F^{m\times n},B\in F^{n\times p}$, we have:
$(AB{)}^T=B^T{A}^T$

proof

$$\begin{array}{rl}(AB{)}_{ij}^T& =(AB{)}_{ji}\\ & =\sum _{k=1}^n{a}_{jk}{b}_{ki}\\ & =\sum _{k=1}^n(A^T{)}_{kj}(B^T{)}_{ik}\\ & =(B^T{A}^T{)}_{ij}\end{array}$$

9. Orthogonal matrix

Let $A\in F^{n\times n}$. $A$ is called an orthogonal matrix if $A^{T}A=I$. Equivalently, $A\in \mathrm{GL}(n,F)$ and $A^{-1}=A^T$.

10. Conjugate

If $F$ is a subfield of $\mathbb{C}$, the conjugate of $a\in F$ is $\overline{a}\in F$.

Let $A=[a_{ij}]\in F^{m\times n}$ be a matrix. The conjugate of $A$ is the matrix $\overline{A}=[\overline{a_{ij}}]\in F^{m\times n}$

• $A,B\in F^{m\times n}$, $\overline{A+B}=\overline{A}+\overline{B}$

• $A\in F^{m\times n},B\in F^{n\times p}$, $\overline{A\cdot B}=\overline{A}\cdot \overline{B}$

11. Hermitian

设 $A=[a_{ij}]\in {\mathbb{C}}^{m\times n}$。$A$ 的共轭转置（conjugate transpose）为

$$A^H:={\overline{A}}^T=[\overline{a_{ji}}]\in {\mathbb{C}}^{n\times m}.$$

将 $A$ 视为线性映射 $A:{\mathbb{C}}^n\to {\mathbb{C}}^m$。相对于两边的标准内积，$A^H$ 表示 $A$ 的伴随映射，即

$$⟨Ax,y⟩=⟨x,A^{H}y⟩,\forall x\in {\mathbb{C}}^n,y\in {\mathbb{C}}^m.$$

这是因为标准内积满足 $⟨u,v⟩=v^{H}u$，所以

$$⟨Ax,y⟩=y^{H}Ax=(A^{H}y{)}^{H}x=⟨x,A^{H}y⟩.$$

特别地，若 $A\in {\mathbb{C}}^{n\times n}$ 满足

$$A^H=A,$$

则称 $A$ 为 Hermitian 矩阵（厄米矩阵）。此时 $A$ 表示 ${\mathbb{C}}^n$ 上的自伴算子；反之，${\mathbb{C}}^n$ 上的线性算子在标准正交基下是自伴的，当且仅当其矩阵是 Hermitian 矩阵。

12. Trace

Let $A=[a_{ij}]\in F^{n\times n}$ be a square matrix. The trace of $A$ is the sum of the diagonal elements of $A$, denoted by $\mathrm{tr}(A)$.

$$\mathrm{tr}(A)=\sum _{i=1}^n{a}_{ii}$$

Properties of Trace

• $\mathrm{tr}(A+B)=\mathrm{tr}(A)+\mathrm{tr}(B)$
• $\mathrm{tr}(cA)=c\mathrm{tr}(A)$
• $\mathrm{tr}(AB)=\mathrm{tr}(BA)$
• $\overline{\mathrm{tr}(A)}=\mathrm{tr}(\overline{A})$
• $\mathrm{tr}(A^T)=\mathrm{tr}(A)$
• 若 $A=[a_{ij}],B=[b_{ij}]\in {\mathbb{C}}^{m\times n}$，则 $\mathrm{tr}(A^{H}B)=\sum _{i=1}^m\sum _{j=1}^n\overline{a_{ij}}{b}_{ij}$

proof : $\mathrm{tr}(AB)=\mathrm{tr}(BA)$

$$\begin{array}{rl}\mathrm{tr}(AB)& =\sum _{i=1}^n(AB{)}_{ii}\\ & =\sum _{i=1}^n\sum _{j=1}^n{a}_{ij}{b}_{ji}\\ & =\sum _{j=1}^n\sum _{i=1}^n{b}_{ji}{a}_{ij}\\ & =\mathrm{tr}(BA)\end{array}$$

13. Inner Product

本节统一采用“第一变量线性、第二变量共轭线性”的约定。

13.1. 向量的标准内积

对任意

$$x=\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right),y=\left(\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right)\in {\mathbb{C}}^n,$$

定义 ${\mathbb{C}}^n$ 上的标准内积为

$$\boxed{⟨x,y⟩=\sum _{i=1}^n{x}_i\overline{y_i}=x^T\overline{y}=y^{H}x.}$$

其中 $y^H={\overline{y}}^T$ 是 $y$ 的共轭转置。该定义满足内积的三条公理。

共轭对称性：

$$\begin{array}{rl}\overline{⟨y,x⟩}& =\overline{\sum _{i=1}^n{y}_i\overline{x_i}}\\ & =\sum _{i=1}^n\overline{y_i}{x}_i\\ & =⟨x,y⟩.\end{array}$$

因此

$$⟨x,y⟩=\overline{⟨y,x⟩}.$$

正定性：

$$⟨x,x⟩=\sum _{i=1}^n{x}_i\overline{x_i}=\sum _{i=1}^n|x_i{|}^2\ge 0,$$

并且

$$⟨x,x⟩=0⟺x_1=\cdots =x_n=0⟺x=0.$$

第一变量线性： 对任意 $a,b\in \mathbb{C}$ 及 $x,w,z\in {\mathbb{C}}^n$，

$$\begin{array}{rl}⟨ax+bw,z⟩& =\sum _{i=1}^n(a{x}_i+b{w}_i)\overline{z_i}\\ & =a⟨x,z⟩+b⟨w,z⟩.\end{array}$$

结合共轭对称性，第二变量相应地满足共轭线性：

$$⟨x,ay+bz⟩=\overline{a}⟨x,y⟩+\overline{b}⟨x,z⟩.$$

在 ${\mathbb{R}}^n$ 中，共轭不起作用，标准内积退化为通常的点积

$$⟨x,y⟩=x^{T}y.$$

13.2. 矩阵的 Frobenius 内积

矩阵空间 ${\mathbb{C}}^{m\times n}$ 也是复向量空间。对 $A=[a_{ij}]$、$B=[b_{ij}]\in {\mathbb{C}}^{m\times n}$，定义

$$\boxed{⟨A,B{⟩}_F:=\mathrm{tr}(B^{H}A)=\mathrm{tr}(A{B}^H)=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}\overline{b_{ij}}.}$$

这一定义与向量标准内积采用相同的变量约定。

共轭对称性：

$$\begin{array}{rl}\overline{⟨B,A{⟩}_F}& =\overline{\mathrm{tr}(A^{H}B)}\\ & =\mathrm{tr}((A^{H}B{)}^H)\\ & =\mathrm{tr}(B^{H}A)\\ & =⟨A,B{⟩}_F.\end{array}$$

第一变量线性：

$$\begin{array}{rl}⟨aA+bB,C{⟩}_F& =\mathrm{tr}(C^H(aA+bB))\\ & =a⟨A,C{⟩}_F+b⟨B,C{⟩}_F.\end{array}$$

第二变量共轭线性：

$$\begin{array}{rl}⟨A,aB+bC{⟩}_F& =\mathrm{tr}((aB+bC{)}^{H}A)\\ & =\overline{a}⟨A,B{⟩}_F+\overline{b}⟨A,C{⟩}_F.\end{array}$$

正定性：

$$\begin{array}{rl}⟨A,A{⟩}_F& =\mathrm{tr}(A^{H}A)\\ & =\sum _{i=1}^m\sum _{j=1}^n|a_{ij}{|}^2\\ & \ge 0,\end{array}$$

且等号成立当且仅当 $A=0$。该内积诱导 Frobenius 范数：

$$\Vert A{\Vert }_F=\sqrt{⟨A,A{⟩}_F}.$$

14. Determinant

14.1. Alternating multilinear map

let $⟨F,V⟩$ be a vector space over $F$. A map $f:V^n\to F$ is called an alternating multilinear map if:

• multilinear: $f$ is linear in each variable
• alternating: $f(v_1,\cdots ,v_i,\cdots ,v_j,\cdots ,v_n)=-f(v_1,\cdots ,v_j,\cdots ,v_i,\cdots ,v_n)$ for any $v_i,v_j\in V$

Let $A=[a_{ij}]\in F^{n\times n}$ be a square matrix. The determinant of $A$ is the scalar $\det (A)$ defined by:

$$|A|:=\det (A)=\sum _{\sigma \in S_n}\mathrm{sgn}(\sigma )\prod _{i=1}^n{a}_{i,\sigma (i)}$$

or equivalently,

$$|A|=\sum _{j_1,j_2,\cdots ,j_n\in [n]}\tau (j_1,j_2,\cdots ,j_n)\prod _{i=1}^n{a}_{i,j_i}$$

where $S_n$ is the symmetric group of degree $n$, $\mathrm{sgn}(\sigma )$ is the sign of the permutation $\sigma$, and $a_{i,\sigma (i)}$ is the element of $A$ at the $i$-th row and $\sigma (i)$-th column.

$$\mathrm{sgn}(\sigma )=\{\begin{array}{ll}{1}_F& \text{if }\sigma \text{ is an even permutation}\\ -1_F& \text{if }\sigma \text{ is an odd permutation}\end{array}$$

$\tau (j_1,j_2,\cdots ,j_n)$ is the number of inverse pairs of the sequence $(j_1,j_2,\cdots ,j_n)$.

It is not difficult to see that:

$$\mathrm{sgn}(\sigma )=(-1{)}^{\tau (j_1,j_2,\cdots ,j_n)}$$

• Determinant is a multilinear map for each row of $A$
• Determinant does not change under transposition, i.e. $\det (A)=\det (A^T)$
• Determinant is a multilinear map for each column of $A$
• Determinant is an alternating multilinear map for both each row of $A$ and each column of $A$
• $\det (A)={\sum }_{j_1,j_2,\cdots ,j_n\in [n]}(-1{)}^{\tau (i_1,i_2,\cdots ,i_n)+\tau (j_1,j_2,\cdots ,j_n)}{\prod }_{k=1}^n{a}_{i_k,j_k}$

14.2. Laplace expansion

$I=i_1,i_2,\cdots ,i_k$
$I^{\prime }=[n]\setminus I$

$J=j_1,j_2,\cdots ,j_k$
$J^{\prime }=[n]\setminus J$

$\sum (X):={\sum }_{x\in X}x$

$A_{I,J}$ is the submatrix of $A$ obtained by deleting the $i$-th $\in I^{\prime }$ row and $j$-th $\in J^{\prime }$ column.

$$\det (A)=\sum _{J\subseteq [n]\wedge |J|=k}(-1{)}^{\sum (I)+\sum (J)}\det (A_{I,J})\det (A_{I^{\prime },J^{\prime }})$$

• $\det (AB)=\det (A)\det (B)$

15. Adjugate matrix

$A_{ij}$ is the submatrix of $A$ obtained by deleting the $i$-th row and $j$-th column.

Let $A=[a_{ij}]\in F^{n\times n}$ be a square matrix. The adjugate of $A$ is the matrix $A^{\text{\#}}:=\mathrm{adj}(A)=[a_{ij}^{\text{\#}}]\in F^{n\times n}$ defined by $a_{ij}^{\text{\#}}=(-1{)}^{i+j}\det (A_{ji})$.

$$A{A}^{\text{\#}}=A^{\text{\#}}A=\det (A)I$$

proof

$$\begin{array}{rl}(A{A}^{\text{\#}}{)}_{ij}& =\sum _{k=1}^n{a}_{ik}{a}_{kj}^{\text{\#}}\\ & =\sum _{k=1}^n{a}_{ik}(-1{)}^{k+j}\det (A_{jk})\\ & =\det (A){\delta }_{ij}\end{array}$$

• $A$ is invertible if and only if $\det (A)\ne 0$
• if $A$ is invertible, then $A^{-1}=\frac{1_F}{\det (A)}{A}^{\text{\#}}$