Matrix

Elementary Matrix

The standard basis of $\mathbb F^n$ is $\{e_i\}_{1\leq i\leq n}$, where $e_i$ is the vector with $1$ in the $i$-th entry and $0$ elsewhere. It holds

$$e_i^\top Ae_j=a_{ij},$$

This can be a test of a linear map $A:\mathbb F^n\to \mathbb F^n$ by the standard basis of $\mathbb F^n$. In total,

$$A=\sum_{i,j=1}^n a_{ij}e_ie^\top_j=\sum_{i,j=1}^n a_{ij}E_{ij},$$

We introduce a kind of basis of $M_n(\mathbb F)=\mathbb F^{n\times n}$ as $\{E_{ij}\}_{1\leq i,j\leq n}$, where $E_{ij}$ is the matrix with $1$ in the $(i,j)$-th entry and $0$ elsewhere, that is so-called elementary matrix, satisfying

$$E_{ij}E_{kl}=\delta_{jk}E_{il},\quad E_{ij}AE_{kl}=a_{jk}E_{il}=:E_{il}\delta_{jk}(A)$$

Generally speaking, left multiplication is to do with the row, and right multiplication is to do with the column, and that is the same with the block matrix.

Sometimes, we use another basis of $M_n(\mathbb F)$, namely

$$\left\{\dfrac {E_{ij}+E_{ji}}2,\dfrac {E_{ij}-E_{ji}}{2}\right\}_{1\leq i< j\leq n}\cup\{E_{ii}\}_{1\leq i\leq n},$$

which is the basis of symmetric and skew-symmetric matrices. It raises the decomposition of $M_n(\mathbb F)$ as a direct sum of symmetric and skew-symmetric matrices.

Rank & Smith Normal Form

Smith Normal Form

For any matrix $A\in M_{m,n}(\mathbb F)$, we can find invertible matrices $P\in M_m(\mathbb F)$ and $Q\in M_n(\mathbb F)$ such that

$$PAQ=\begin{pmatrix}I_r&O\\O&O\end{pmatrix},$$

where $r$ is the rank of $A$ and $O$ can be a zero matrix of any size(including $0\times 0$). This is called the Smith normal form of $A$. It can be proved by using the Gauss elimination method(that is, elementary row and column operations).

Moore-Penrose Inverse*

The row rank and column rank of a matrix are equal, which is the rank of the matrix. If $A$ is full rank on row(column), then as a linear map, $A$ is surjective(injective), and it has a right(left) inverse called the Moore-Penrose inverse,

$$A^+=A^\top(AA^\top)^{-1}\quad \quad A^+=(A^\top A)^{-1}A^\top.$$

It’s compat with the inverse of a square matrix.

Criterion of Rank

As the determinant can tell whether a square matrix is full rank or not, for any $m\times n$ matrix $A$, we also hold that

$$\mathrm{rank}\ A=\mathrm{rank}\ A^\top A=\mathrm{rank}\ AA^\top,$$

allowing us to use the determinant on $A^\top A$ or $AA^\top$ to tell whether $A$ is full rank or not.

Singular Value Decomposition

Similar to the Smith normal form, for matrix $A\in M_{m,n}(\mathbb C)$, we can find $P\in U(m)$ and $Q\in U(n)$ such that

$$PAQ=\begin{pmatrix}\Sigma&O\\O&O\end{pmatrix},$$

where $\Sigma$ is a diagonal matrix with positive entries $\sigma_1\geq \sigma_2\geq \cdots\geq \sigma_r>0$ and $r$ is the rank of $A$, satisfying that

$$\sigma_i^2=\lambda_i(AA^\top)=\lambda_i(A^\top A),$$

where $\lambda_i$ is the $i$-th eigenvalue of the matrix. This is called the singular value decomposition of $A$. The case of $A\in M_{m,n}(\mathbb R)$ is similar, with $P\in O(m)$ and $Q\in O(n)$.

Adjoint Matrix & Inverse Matrix

Adjoint Matrix

Inspired by the Laplace theorem, we define the adjoint matrix of $A\in M_n(\mathbb F)$ as

$$A^*=\begin{pmatrix}A_{11}&A_{21}&\cdots&A_{n1}\\A_{12}&A_{22}&\cdots&A_{n2}\\\vdots&\vdots&\ddots&\vdots\\A_{1n}&A_{2n}&\cdots&A_{nn}\end{pmatrix},$$

where $A_{ij}$ is the algebraic cofactor of $a_{ij}$. Be aware that $A^*$ is the transpose of the cofactor matrix of $A$. Then

$$AA^*=A^*A=|A|I_n.$$

Whether $A$ is invertible or not, we can prove

$$(AB)^*=B^*A^*,$$

by using the Cauchy-Binet formula or perturbation method if $\mathbb F\subseteq \mathbb C$.

With the Smith normal form, $A^*$ is non-zero if and only if the rank of $A$ is no less than $n-1$. When $\mathrm{rank}\ A=n-1$, $A^*$ is a non-zero matrix of rank $1$. So the polynomial map $A\mapsto A^*$ is injective only when $n=1,2$.

Perturbation Method on $\mathbb C$

View $|xI_n-A|$ as a polynomial of $x$, the zeros of the polynomial are finite so that isolated. So under the $\|\cdot\|_\infty$ norm, there exists $\varepsilon_0>0$ such that for any $0<\varepsilon<\varepsilon_0$, it holds

$$|A+\varepsilon I_n|\neq 0,\quad \|A+\varepsilon I_n-A\|_\infty=\|\varepsilon I_n\|_\infty=\varepsilon\to 0.$$

So invertible matrices are dense in $M_n(\mathbb C)$, which leads to the perturbation method.

For instance, on $\mathbb C$, the adjoint matrix of $A$ can be represented as a polynomial(related to the characteristic polynomial) of $A$ by the Cayley-Hamilton theorem because it holds on invertible matrices on any field.

Generally, the operation on matrices are mostly polynomial on the entries of the matrices, in this case, the perturbation method is available.

Semi-positive definite matrix is the limit of positive definite matrix.

Inverse Matrix

Adjoint matrix gives a way to compute the inverse of a matrix, that is

$$A^{-1}=A^*|A|^{-1}.$$

Besides, we can also compute the inverse of a matrix by using the Gauss elimination method.

Sherman-Morrison-Woodbury-Hua formula states that if $A\in M_n(\mathbb F),\ C\in M_m(\mathbb F)$ are invertible, then for any $B\in M_{m,n}(\mathbb F),\ D\in M_{n,m}(\mathbb F)$ satisfying that $C^{-1}+DA^{-1}B$ is invertible, it holds that

$$(A+BCD)^{-1}=A^{-1}-A^{-1}B(C^{-1}+DA^{-1}B)^{-1}DA^{-1}.$$

It is from an observation that

$$(I+BA)^{-1}=I-B(I+AB)^{-1}A,$$

for any $A\in M_{m,n}(\mathbb F),\ B\in M_{n,m}(\mathbb F)$ such that $I+AB$ is invertible.

Especially, if $A\in M_n(\mathbb F)$ is invertible, then for any $u,v\in \mathbb F^n$ such that $1+v^\top A^{-1}u\neq 0$, it holds that

$$(A+uv^\top)^{-1}=A^{-1}-\frac{A^{-1}uv^\top A^{-1}}{1+v^\top A^{-1}u}.$$

Companion Matrix

Companion Matrix

Given a polynomial $p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\in\mathbb F[x]$, the companion matrix of $p(x)$ is defined as

$$C(p)=\begin{pmatrix}0&1&0&\cdots&0\\0&0&1&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&\cdots&1\\-a_0&-a_1&-a_2&\cdots&-a_{n-1}\end{pmatrix}.$$

The characteristic polynomial of $C(p)$ satisfies

$$\det (xI-C(p))=p(x),$$

and it’s also the minimal polynomial of $C(p)$.

Frobenius Normal Form*

The companion matrix $C(p)$ is also called the Frobenius normal form of the polynomial $p(x)$. Under $C(p)^\top$, $e_1$ is a cyclic vector, that is

$$\{e_1,C(p)^\top e_1,\cdots,(C(p)^\top)^{n-1}e_1\}$$

contains a basis of $\mathrm{Im}\ C(p)^\top$.

Recurrence Relation

Consider a recurrence relation in $\mathbb C$

$$x_{p+n}=a_{n-1}x_{p+n-1}+a_{n-2}x_{p+n-2}+\cdots+a_1x_{p+1}+a_0x_p,\quad p\geq 0.$$

By the property of companion matrix and Jordan canonical form, we find the closed form of the sequence $\{x_n\}$ is

$$x_m=\sum^k_{j=1}P_j(m)\lambda^m_j,$$

where $\lambda_j$ is the eigenvalue of the polynomial

$$p(x)=x^n-a_{n-1}x^{n-1}-\cdots-a_1x-a_0,$$

and $P_j(m)$ is a polynomial of degree not greater than $m_j-1$ with $m_j$ the algebraic multiplicity of $\lambda_j$. Once we know $n$ initial values (not neccessarily from the starter of the sequence), we can determine the coefficients of $P_j(m)$ by the property of generalized Vandermonde matrix.

Similarity & Jordan Canonical Form

Matrix Function

Jordan Canonical Form

Polynomial

Define a polynomial of degree $n$ over a field $\mathbb F$ as

$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\in \mathbb F[x],\quad a_n\neq 0.$$

For convenience, we denote

$$g(x)=b_mx^m+b_{m-1}x^{m-1}+\cdots+b_1x+b_0\in \mathbb F[x],\quad b_m\neq 0,$$

for use later in this section.

View as a Vector Space

View as a Ring

Bezout Theorem

Bezout Theorem states that for any two elements $x,y$ in a principal ideal domain $R$, there exists $a,b\in R$ such that

$$ax+by=\gcd(x,y).$$

Note that $\mathbb F[x]$ is a PID.

Sylvester Matrix

By the algebraic extension and the minimal polynomial, we can develop the Sylvester matrix, which is defined by given $f(x),g(x)\in \mathbb F[x]$ as

$$S(f,g)=\begin{pmatrix}a_n&a_{n-1}&\cdots&a_0&0&\cdots&0\\0&a_n&a_{n-1}&\cdots&a_0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\0&0&0&\cdots&a_n&a_{n-1}&\cdots&a_0\\b_m&b_{m-1}&\cdots&b_0&0&\cdots&0\\0&b_m&b_{m-1}&\cdots&b_0&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\0&0&0&\cdots&b_m&b_{m-1}&\cdots &b_0 \end{pmatrix},$$

where the first $m$ rows are the coefficients of $f(x)$ and the last $n$ rows are the coefficients of $g(x)$. The determinant of Sylvester matrix is called the resultant of $f(x)$ and $g(x)$, denoted as $\text{Res}(f,g)$, used to determine whether $f(x)$ and $g(x)$ have a common root or not.

Determinant

View as a Combinatorial Object

Combinatorial Definition

The combinatorial definition of determinant is

$$\det A=\sum_{\sigma\in S_n}\text{sgn}(\sigma)\prod^n_{i=1}a_{i,\sigma(i)},$$

where $S_n$ is the set of all permutations of $\{1,2,\cdots,n\}$, and $\text{sgn}(\sigma)$ is the sign of permutation $\sigma$.

Laplace Theorem

Laplace theorem states that let $|A|$ be the determinant of order $n$. Fix $m$ rows, $1\leq m\leq n$, then

$$|A|=\sum_{1\leq k_1 < k_2 < \cdots < k_m\leq n}A\left(\begin{matrix}i_1&i_2&\cdots&i_m\\j_1&j_2&\cdots&j_m\end{matrix}\right)\hat A\left(\begin{matrix}i_1&i_2&\cdots&i_m\\j_1&j_2&\cdots&j_m\end{matrix}\right),$$

where let $i_{m+1} $$\hat A\left(\begin{matrix}i_1&i_2&\cdots&i_m\\j_1&j_2&\cdots&j_m\end{matrix}\right)=(-1)^{\sum_{c=1}^m(i_c+j_c)}A\left(\begin{matrix}i_{m+1}&i_{m+2}&\cdots&i_n\\j_{m+1}&j_{m+2}&\cdots&j_n\end{matrix}\right).$$

As a corollary, we have the expansion of determinant along a row or column and raise the inductive definition of determinant.

Cauchy-Binet Formula

By using the Laplace theorem, we can show the Cauchy-Binet formula. Let $A\in M_{m,n}(\mathbb F)$ and $B\in M_{n,m}(\mathbb F)$, then

$$|AB|=\sum_{1\leq j_1 where $m\leq n$. For $m>n$, we have $|AB|=0$.

More generally, Cauchy-Binet formula can be used to compute the subdeterminant with order $r$ of the product of two matrices $A\in M_{m,n}(\mathbb F)$ and $B\in M_{n,m}(\mathbb F)$, where $1\leq r\leq \min\{m,n\}$, as follows

$$AB\left(\begin{matrix}i_1&i_2&\cdots&i_r\\j_1&j_2&\cdots&j_r\end{matrix}\right)=\sum_{1\leq k_1 while $r>\min\{m,n\}$, the subdeterminant of $AB$ with order $r$ is zero.

It raise a fundamental property of $A,B\in M_n(\mathbb F)$, that is

$$|AB|=|A||B|,$$

by a combinatorial method.

View as a Polynomial of several variables

Vieta Formula

By applying the Laplace theorem, for an $n\times n$ matrix $A=(a_{ij})$, we can show the coefficients of

$$|xI_n-A|=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$

satisfy the Vieta formula

$$a_{n-k}=(-1)^k\sum_{1\leq i_1<\cdots where $\lambda_i$ is the eigenvalue of $A$.

Vandermonde Matrix

Vandermonde matrix is defined as

$$V(x)=\begin{pmatrix}1&x_1&x^2_1&\cdots&x^{n-1}_1\\1&x_2&x^2_2&\cdots&x^{n-1}_2\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x^2_n&\cdots&x^{n-1}_n\end{pmatrix},$$

with the determinant

$$|V(x)|=\prod_{1\leq i

We can show that one $n$-th degree polynomial is uniquely determined by $n+1$ points by Vandermonde matrix as follows

$$V(x)\begin{pmatrix}a_0\\a_1\\\vdots\\a_n\end{pmatrix}=\begin{pmatrix}y_0\\y_1\\\vdots\\y_n\end{pmatrix},$$

so that the $n$-th degree polynomial $p(x)$ satisfying

$$p(x_i)=y_i,\quad i=0,1,\cdots,n,$$

is uniquely determined by the coefficients $a_0,a_1,\cdots,a_n$. In fact, the method of Vandermonde matrix takes $\{1,x,x^2,\cdots,x^n\}$ as the basis of $P_n[x]$.

In another view, we can introduce the Lagrange interpolation polynomial

$$p(x)=\sum^n_{i=0}y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}.$$

It is the same polynomial as the one determined above. In fact, the Lagrange interpolation polynomial takes $\{\prod_{j\neq i}(x-x_j)\}_{i=0}^n$ as the basis of $P_n[x]$.

Apply the Lagrange interpolation polynomial again, it holds that

$$x^k=\sum^n_{i=0}x^k_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j},\quad k=0,1,\cdots,n,$$

which implies the transition matrix between two bases is just the Vandermonde matrix $V(x)$.

As an application, we define the resultant of two polynomials $f(x)=a_nx^n+\cdots+a_1x+a_0$ and $g(x)=b_mx^m+\cdots+b_1x+b_0$ as

$$\text{Res}(f,g)=a^m_nb^n_m\prod_{i=1}^n\prod_{j=1}^m(\alpha_i-\beta_j),$$

where $\alpha_i$ and $\beta_j$ are the roots of $f(x)$ and $g(x)$ respectively. The resultant can be computed by the determinant of Sylvester matrix

Generalized Vandermonde matrix is defined as

$$V(m,\lambda)=(V_1(\lambda_1),V_2(\lambda_2),\ldots,V_k(\lambda_k)),$$

where $V_i(\lambda_i)$ is a matrix of size $n\times r_i$ with $\sum^k_{i=1}r_i=n$ and $k$ the number of distinct eigenvalues. The matrix $V_i(\lambda_i)$ is defined as

$$V_i(\lambda_i)=\begin{pmatrix}\lambda_i^{m_1}& m_1\lambda_i^{m_1}&\cdots& m_1^{r_i-1}\lambda_i^{m_1}\\\lambda_i^{m_2}& m_2\lambda_i^{m_2}&\cdots &m_2^{r_i-1}\lambda_i^{m_2}\\\vdots&\vdots&\ddots&\vdots\\\lambda_i^{m_n}& m_n\lambda_i^{m_n}&\cdots &m_n^{r_i-1}\lambda_i^{m_n}\end{pmatrix}.$$

The determinant of $V(m,\lambda)$ is

$$\det V(m,\lambda)=\prod^k_{i=1}\prod_{1\leq jNewton Formula

For $n$ variables $x_1,x_2,\cdots,x_n$, we define the $k$-th power sum as

$$s_k=\sum^n_{i=1}x^k_i.$$

A special case of Hankel matrix is defined as

$$H_k=\begin{pmatrix}s_0&s_1&s_2&\cdots&s_{k-1}\\s_1&s_2&s_3&\cdots&s_k\\s_2&s_3&s_4&\cdots&s_{k+1}\\\vdots&\vdots&\vdots&\ddots&\vdots\\s_{k-1}&s_k&s_{k+1}&\cdots&s_{2k-2}\end{pmatrix}=V(x)^\top V(x).$$

Resultant

Root Method

多项式的整性 Factor

In some degree, there are lots of symmetric or cyclic structures in the determinant, we can consider the determinant as a polynomial of several variables, and find the factors of the polynomial by considering some special values of(relation between) the variables. If necessary, once the polynomial of determinant is found, we can consider some special values of the variables to find the coefficients.

Low Order Formula

Given two square matrices $A,D\in M_n(\mathbb F)$, it holds that

$$\left|\begin{matrix}A& B\\C& D\end{matrix}\right|=|A||D-C A^{-1}B|=|D||A-B D^{-1}C|,$$

if $A$ and $D$ are invertible. This is called the low order formula of determinant.

As a corollary, Sylvester’s determinant theorem states that

$$|\lambda I_n- AB|=|\lambda I_m- BA|,$$

where $A\in M_{m,n}(\mathbb F)$ and $B\in M_{n,m}(\mathbb F)$. Similarly, it holds that

$$|A+UV|=|A||I+VA^{-1}U|,$$

where $A\in M_n(\mathbb F)$ is invertible, $U\in M_{n,m}(\mathbb F)$ and $V\in M_{m,n}(\mathbb F)$.

Induction

View as a Geometric Object

Whether the determinant is zero or not is related to the linear independence of the column(row) vectors of the matrix. The absolute value of the determinant represents the volume of the parallelepiped spanned by the column(row) vectors of the matrix. It holds that

$$|AB|=|A||B|,$$

shown by integration by substitution, which naturally explains why the determinant is multiplicative and commutative.

View as a Multilinear Function

Let $f:M_n(\mathbb F)\to \mathbb F$ be a map, such that for any $A,B,C\in M_n(\mathbb F)$, it holds that

  1. If the $i$-th column of $A$ is the sum of the $i$-th column of $B$ and $C$, and the other columns of $A$ are the same as those of $B$ and $C$, then $f(A)=f(B)+f(C)$.
  2. If the $i$-th column of $A$ is the scalar multiple of the $i$-th column of $B$ with a scalar $k\in \mathbb F$, and the other columns of $A$ are the same as those of $B$, then $f(A)=kf(B)$.
  3. If exchanging the $i$-th and $j$-th columns of $A$ gives $B$, then $f(A)=-f(B)$.
  4. $f(I_n)=1$.

Then $f(A)=|A|$ for any $A\in M_n(\mathbb F)$, and the determinant is the unique function satisfying the above four properties.

Similarly, there is also axiom of the trace of a matrix, which is the unique function satisfying the following properties

Trace

Frobenius Norm

For any $A\in M_{m\times n}(\mathbb C)$, it holds that

$$\|A\|_{\mathrm{F}}=\sqrt{\mathrm{Tr}(AA^\dagger)}=\sqrt{\sum^m_{i=1}\sum^n_{j=1}|a_{ij}|^2}\geq 0,$$

and it has a kind of positive definiteness, so that in another view, it can be seen as the Frobenius norm of $A$.

Note that the trace is the sum of the minors of order $1$ of the matrix, so in general, we define the $k$-th order trace of a matrix $A\in M_n(\mathbb F)$ as

$$\mathrm{Tr}_k(A)=\sum_{1\leq i_1<\cdots that is the sum of the minors of order $k$ of the matrix. By the Cauchy-Binet formula, we have the same result with $AA^\dagger$.

And there is no surprise that the $n$-th order trace of a matrix is just the determinant of the matrix. Moreover, they can be seen as the coefficients of the characteristic polynomial of the matrix, by the Vieta formula

$$\det(xI_n-A)=x^n-\mathrm{Tr}_1(A)x^{n-1}+\mathrm{Tr}_2(A)x^{n-2}-\cdots+(-1)^n\mathrm{Tr}_n(A).$$

By view of the Descartes rule of signs, we find that the real eigenvalues of $AA^\dagger$ are all non-negative, without computing them. As a corollary, we have proved the Sylvester’s determinant theorem.

View as a Multilinear Function

Let $f:M_n(\mathbb F)\to \mathbb F$ be a map, such that for any $A,B\in M_n(\mathbb F)$, it holds that

  1. $f(A+B)=f(A)+f(B)$.
  2. $f(kA)=kf(A)$ for any $k\in \mathbb F$.
  3. $f(AB)=f(BA)$.
  4. $f(I_n)=n$.

Then $f(A)=\mathrm{Tr}(A)$ for any $A\in M_n(\mathbb F)$, and the trace is the unique function satisfying the above four properties.

The third property can be generalized to trace with order $r$. That is

$$\mathrm{Tr}_r(AB)=\mathrm{Tr}_r(BA),$$

and $r=n$ is the determinant of the matrix. You can check other properties of the trace with order $r$ by using the Cauchy-Binet formula, find out what is the common property of the trace with order $r$ and the determinant.

Space & Operators

chap3.1 跳过

Linear Operator

Rank & Linear Independence

When only do row(column) operations on a matrix to make it an echelon form, the columns(rows) of the original matrix corresponding to the pivot columns(rows) of the echelon form are linearly independent. It is from a simply fact that a set of linear independent(dependent) vectors maintains linear independent(dependent) after an extension(restriction) on the dimension.

With this fact, the rank of a matrix is $r$ if and only if there exists a cofactor of order $r$ of the matrix is non-zero, and all cofactors of order more than $r$ are zero.

Linear Extension & Representation

For a linear map $T:V\to W$, the relationship on the basis of $V$ and $W$ contains all information of $T$. That is the extension from the basis of $V$ to the whole space $V$ is linear. So we introduce the representation of $T$ on the basis of $V$ and $W$, which is a matrix $A\in M_{m,n}(\mathbb F)$, such that

$$T(v_j)=\sum^m_{i=1}a_{ij}w_i,\quad j=1,2,\cdots,n,$$

where $\{v_j\}_{j=1}^n$ and $\{w_i\}_{i=1}^m$ are the basis of $V$ and $W$ respectively. With these basis, we can describe a vector by its coordinates.

Linear Space

Linear Extension

Dimension Formula of Intersection

It holds that

$$\dim(U+W)=\dim U+\dim W-\dim(U\cap W),$$

where $U$ and $W$ are subspaces of a linear space $V$. It can be proved by using the basis of $U\cap W$ and extending it to the basis of $U$ and $W$ respectively.

Solution Space of Linear Equation

The rank-nullity theorem states that for a linear map $T:V\to W$, it holds that

$$\dim V=\dim \ker T+\dim \mathrm{Im}\ T.$$

Let $A$ be the representation of $T$ on the basis of $V$ and $W$, then the structure of the solution space of a linear equation $Ax=b$, that is,

$$x_0+y,\quad Ax_0=b,\ y\in \ker A,$$

where $x_0$ is a particular solution of the linear equation. The quotient space

$$V/\ker A\cong \mathrm{Im}\ A$$

Symmetric Space

Symmetric Matrix & $AA^\dagger$

Skew-Symmetric Space

Ex2.5

Act on Basis

Act on basis

Representation of Matrix

Root Space

Given a basis of a linear space $V$, the representation of a linear operator $\varphi:V\to V$ is a matrix $A\in M_n(\mathbb F)$. The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of the eigenspace

$$V_\lambda=\ker (A-\lambda I_n),$$

so $\dim V_\lambda=\dim \ker (A-\lambda I_n)= n-\mathrm{rank}(A-\lambda I_n)$. The algebraic multiplicity of an eigenvalue $\lambda$ is

$$R_\lambda=\bigcup_{k=1}^\infty \ker (A-\lambda I_n)^k.$$

Note that the ascending chain of subspaces, we can compute

DONTFORGET

Induction, Symmetric

Complementary

Trigonometric Functions and Exponential Functions

Euler’s formula states that

$$e^{ix}=\cos x+i\sin x.$$

Conversely, we have

$$\cos x=\frac{e^{ix}+e^{-ix}}{2},\quad \sin x=\frac{e^{ix}-e^{-ix}}{2i}.$$

More generally, De Moivre’s formula states that

$$(\cos x+i\sin x)^n=\cos nx+i\sin nx.$$

Closed Properties

Besides trivial results, what need notice is that:

  • Up-triangle matrix, lower-triangle matrix is closed under adjoint and inverse.

双线性和基变换

迷向空间和正负惯性

辛基和正交基的构造，变换的来历

CheatSheet

Inverse

Note that for a block matrix $S$ satisfying that $A$ and $D-CA^{-1}B$ are invertible, it holds that

$$S=\begin{pmatrix}A&B\\C&D\end{pmatrix},\quad S^{-1}=\begin{pmatrix}A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}&-A^{-1}B(D-CA^{-1}B)^{-1}\\-(D-CA^{-1}B)^{-1}CA^{-1}&(D-CA^{-1}B)^{-1}\end{pmatrix}.$$

This result can be done by simply doing block matrix multiplication, and it raises

  • The low order formula of determinant, that is $$\left|\begin{matrix}A&B\\C&D\end{matrix}\right|=|A||D-CA^{-1}B|=|D||A-BD^{-1}C|.$$
  • The low order formula of positive/negative inertia, that is when $S$ is Hermitian or symmetric $$\pi_\pm(S)=\pi_\pm(A)+\pi_\pm(D-CA^{-1}C^\dagger)=\pi_\pm(D)+\pi_\pm(A-C^\dagger D^{-1}C).$$

1

(Skew-)Symmetric Space with Trace

Symmetric space is a linear space with a symmetric bilinear form. For the one over $\mathbb R$ or $\mathbb C$, the element of which can be represented as a symmetric or Hermitian matrix. That is, for $g:V\times V\to \mathbb R$(same for $\mathbb C$), it holds that

$$g(x,y)=x^\dagger A y,$$

where $x,y\in \mathbb R^n$ are coordinates of the basis of $V$ and $A=(g(e_i,e_j))_{n\times n}\in M_n(\mathbb R)$. Let

$$\mathrm{tr}_k(A)=\sum_{1\leq i_1 < \cdots < i_k\leq n}A\left(\begin{matrix}i_1&i_2&\cdots&i_k\\i_1&i_2&\cdots&i_k\end{matrix}\right),$$

By the Cauchy-Binet formula and the Cholesky decomposition, for positive definite matrix $A$, we have $A=LL^\dagger$

$$\mathrm{tr}_k(A)=\mathrm{tr}_k(LL^\dagger)=\sum_{\substack{1\leq i_1 < \cdots < i_k\leq n\\1\leq j_1 < \cdots < j_k\leq n}}L\left(\begin{matrix}i_1&i_2&\cdots&i_k\\j_1&j_2&\cdots&j_k\end{matrix}\right)L^\dagger\left(\begin{matrix}j_1&j_2&\cdots&j_k\\i_1&i_2&\cdots&i_k\end{matrix}\right)\geq 0,$$

where the equality holds if and only if the rank of $A$ is less than $k$. Combine with $\mathrm{r}(A)=\mathrm{r}(AA^\dagger)$ for any $A\in M_{m,n}(\mathbb F)$, we can use the $k$-th order trace to determine the rank of a matrix. As $k=1$, the condition of the equality is $A=O$ and that of $k=n$ is $|A|=0$. By the Laplace theorem, for $1\leq k\leq n$

$$\mathrm{tr}_k(A+B)=\sum_{|\alpha|=k}\sum_{\substack{\beta,\gamma\subset \alpha\\ |\beta|=|\gamma|}}A\left(\begin{matrix}\beta\\\gamma\end{matrix}\right)\hat B_{[\alpha]}\left(\begin{matrix}\beta\\\gamma\end{matrix}\right),$$

where $\alpha,\beta,\gamma$ are all sequences of indices in $[n]$. The trace is linear only when $k=1$, and it introduces the Frobenius norm of a matrix $A\in M_{m,n}(\mathbb F)$. Since(same for $\mathbb R$)

$$M_n(\mathbb C)=\{A\in M_n(\mathbb C):A=A^\dagger\}\oplus \{A\in M_n(\mathbb C):A=-A^\dagger\},$$

under this basis, the Frobenius norm of a matrix is the sum of the Frobenius norms of its symmetric and skew-symmetric parts. And with this basis, we develop sub(semi-)positive definite matrix with $\alpha^\dagger A\alpha(\geq )>0$ and may not be symmetric, which can be represented by the sum of (semi-)positive matrix and skew symmetric one.

Decomposition

QR & Gram-Schmidt

That a symmetric matrix $A\in M_n(\mathbb C)$ is (semi-)positive definite is equivalent to that

  • $A=L D L^\dagger$ with $L$ an lower-triangle matrix with diagonal entries $1$ and $D$ a diagonal matrix with (non-negative) positive entries.(LDL)
  • $A=L L^\dagger$ with $L$ a lower-triangle matrix with (non-negative) positive diagonal entries.(Cholesky)
  • $A=CC^\dagger$ with $C$ a (non-)invertible matrix.(Conjugate)

When $A$ is positive definite, the first two decompositions are unique. As for QR decomposition, it is a decomposition of a matrix $A\in M_{m,n}(\mathbb F)$ as follows, by applying the Gram-Schmidt process

$$A=QR,$$

where $Q\in M_{m,n}(\mathbb F)$ is a matrix with orthonormal columns, and $R\in M_n(\mathbb F)$ is an upper-triangle matrix with positive diagonal entries. So they have a relationship as follows

$$\text{Positive Definite: Cholesky}\ll \text{Symmetric: LDL}\ll \text{General: QR},$$

for symmetric matrix, $D$ in LDL decomposition is the diagonal matrix determined by its inertia.

Spectral & Polar & SVD

Let $V$ be an $n$-dimensional inner product space over $\mathbb F$. If $V$ is Euclidean and $A\in M_n(\mathbb R)$ is a symmetric matrix, or if $V$ is unitary and $A\in M_n(\mathbb C)$ is a Hermitian matrix, then there exists an orthonormal basis of $V$ consisting of eigenvectors of $A$. That is

$$\varphi = \lambda_1 P_1+\lambda_2 P_2+\cdots+\lambda_k P_k,$$

where $\varphi:V\to V$ is a linear operator with representation $A$, $\lambda_i$ is the eigenvalue of $\varphi$ and $P_i:V\to V$ is the orthogonal projection onto the eigenspace corresponding to $\lambda_i$. The decomposition of $\varphi$ is called the spectral decomposition.

As a generalization of the polar decomposition of a complex number, for any $A\in M_n(\mathbb C)$, there exists a unitary matrix $U\in M_n(\mathbb C)$ and a positive semi-definite matrix $P\in M_n(\mathbb C)$ such that

$$A=UP.$$

It is the same for $M_n(\mathbb R)$, with $U$ an orthogonal matrix and $P$ a positive semi-definite matrix. The choice of $P$ is unique, and $U$ is unique if $A$ is invertible. The polar decomposition can be obtained by the spectral decomposition of $AA^\dagger$.

Split into Direct Sum

Proper Subspace Coverage

For finite proper subspaces of a vector space, there exists a vector not in any of them. With this lemma

  • If $g$ is a bilinear form on a vector space $V$ over a field $\mathbb F$, and for any $x,y\in V$, it holds that $x\perp y$ if and only if $y\perp x$, then $g$ is symmetric or skew-symmetric.
  • Linear operator $\varphi:V\to V$ on a vector space $V$ over a field $\mathbb F$ satisfying $\varphi^2=\varphi$, then $V=\ker \varphi\oplus \mathrm{im}\ \varphi$.

Tips

  • For problems with positive definite matrices, since it has a relationship with sequential principal minors, we can consider take induction from the last $n$-th row and column.
  • Before handling a problem, see whether it remains unchanged after some transformation, such as row/column operations, similarity/conjugate transformation, etc. If so, we can consider the problem in a simplified form.
  • When using the change of variable method to compute the normal form of a symmetric form, check whether the transformation matrix is invertible or not.
  • The minor of a matrix is unchanged under the third type of elementary row/column operations among the row/column (non-)contained in the minor, which leads to the sequential principal minor method to check whether a matrix is positive definite or not, and the strict diagonal dominance method to construct a positive definite matrix.

Macmahon Master Theorem

Exercises

From Textbook Xie

Ex1.4. Compute the determinant below

$$|A|=\left|\begin{matrix}a_1& b_2&b_3&\cdots&b_n\\c_2&a_2&0&\cdots&0\\c_3&0&a_3&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\c_n&0&0&\cdots&a_n\end{matrix}\right|$$

No matter $a_i$ is zero or not, it holds that

$$|A|=\prod^n_{i=1}a_i-\sum^n_{i=2}a_2\cdots a_{i-1}b_ic_i a_{i+1}\cdots a_n.$$

Just replace $a_i$ with $b_ic_i$ in the second term for $i=2,3,\cdots,n$.

Ex1.16 & Ex1.23. Compute the determinant as follows

$$D_n=\left|\begin{matrix}x_1& y&y&\cdots&y\\z&x_2&y&\cdots&y\\ z &z&x_3&\cdots&y\\\vdots&\vdots&\vdots&\ddots&\vdots\\z&z&z&\cdots&x_n\end{matrix}\right|.$$

When $y=z$, we have

$$D_n=\left(1+\sum^n_{i=1}\frac{y}{x_i-y}\right)\prod^n_{i=1}(x_i-y).$$

When $y\neq z$, we have

$$D_n=\dfrac 1{z-y}\left(z\prod^n_{i=1}(x_i-y)-y\prod^n_{i=1}(x_i-z)\right).$$

Ex1.18. Cauchy matrix is defined as

$$C(x,y)=\left(\frac{1}{x_i+y_j}\right)_{1\leq i,j\leq n},$$

with the determinant

$$\det C(x,y)=\frac{\prod_{1\leq i

Ex1.24. $f_1,f_2,\cdots,f_n\in \mathbb F[x]$ are $n$ polynomials of degree not greater than $n-2$. Show that for any $a_1,a_2,\cdots,a_n\in \mathbb F$, it holds that

$$\left|\begin{matrix}f_1(a_1)&f_2(a_1)&\cdots&f_n(a_1)\\f_1(a_2)&f_2(a_2)&\cdots&f_n(a_2)\\\vdots&\vdots&\ddots&\vdots\\f_1(a_n)&f_2(a_n)&\cdots&f_n(a_n)\end{matrix}\right|=0.$$

Ex1.33. Show that

$$|A|=\left|\begin{matrix} 0 & a_1+a_2 & \cdots & a_1+a_{n-1}& a_1+a_n\\ a_2+a_1 & 0 & \cdots & a_2+a_{n-1} & a_2+a_n\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{n-1}+a_1 & a_{n-1}+a_2 & \cdots & 0 & a_{n-1}+a_n\\ a_n+a_1 & a_n+a_2 & \cdots & a_n+a_{n-1} & 0\end{matrix}\right|$$

has a closed form

$$|A|=(-2)^{n-2}\prod^n_{i=1}a_i\left[(n-2)^2-\left(\sum^n_{i=1}\frac 1{a_i}\right)\left(\sum^n_{i=1}a_i\right)\right].$$

Ex1.46. Show that for $n$ square matrices $A,B$, it holds that

$$|A+B|=|A|+|B|+\sum_{k=1}^{n-1}\sum_{\substack{1\leq i_1 < \cdots < i_k\leq n\\1\leq j_1 < \cdots < j_k\leq n}}A\left(\begin{matrix}i_1&\cdots&i_k\\j_1&\cdots&j_k\end{matrix}\right)\hat B\left(\begin{matrix}i_1&\cdots&i_k\\j_1&\cdots&j_k\end{matrix}\right).$$

More generally, consider trace of order $r$ of a matrix, we have

$$\mathrm{Tr}_r(A+B)=\mathrm{Tr}_r(A)+\mathrm{Tr}_r(B)+\sum_{k=1}^{r-1}\sum_{|\alpha|=k}\sum_{\substack{\beta,\gamma\subseteq \alpha\\|\beta|=|\gamma|=k}}A\left(\begin{matrix}\beta\\\gamma\end{matrix}\right)\hat B_{[\alpha]}\left(\begin{matrix}\beta\\\gamma\end{matrix}\right),$$

where $\hat B_{[\alpha]}$ is the submatrix of $B$ with rows and columns indexed by $\alpha$.

Ex2.13. Let $A\in M_2(\mathbb F)$, if $A^n=O$, show that $A^2=O$.

Ex2.16. Compute the inverse of the following matrix

$$A=\begin{pmatrix}0&1&1&\cdots&1\\1&0&1&\cdots&1\\1&1&0&\cdots&1\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&1&1&\cdots&0\end{pmatrix}=-I_n+\dfrac 1{n-1}\begin{pmatrix}1&1&1&\cdots&1\\1&1&1&\cdots&1\\1&1&1&\cdots&1\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&1&1&\cdots&1\end{pmatrix}.$$

Ex2.17.

Ex2.34. Show that the inverse of the following matrix

$$A=\begin{pmatrix}1&2&3&\cdots&n\\n&1&2&\cdots&n-1\\n-1&n&1&\cdots&n-2\\\vdots&\vdots&\vdots&\ddots&\vdots\\2&3&4&\cdots&1\end{pmatrix}$$

is

$$A^{-1}=\dfrac 1{ns}\begin{pmatrix}1-s&1+s&1&\cdots&1\\1&1-s&1+s&\cdots&1\\1&1&1-s&\cdots&1+s\\\vdots&\vdots&\vdots&\ddots&\vdots\\1+s&1&1&\cdots&1-s\end{pmatrix},$$

where $s=n(n+1)/2$.

Ex2.56. Compute the following determinant in $\mathbb C$

$$A=\left|\begin{matrix}a_1& a_2&\cdots&a_n\\ a_n& a_1&\cdots&a_{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ a_2& a_3&\cdots&a_1\end{matrix}\right|=\prod^n_{j=1}f(\omega^j),$$

where $f(x)=a_1+a_2x+\cdots+a_nx^{n-1}$ and $\omega$ is the $n$-th root of unity(which generates the eigenvalues of the circulant matrix $J_n$). As an example, when $a_k=\cos k\theta$ for some $\theta\in\mathbb R$, we have

$$A=2^{n-2}\sin^{n-2}\dfrac {n\theta}2\left(\sin^n\dfrac {(n+2)\theta}2-\sin^n\dfrac {n\theta}2\right).$$

Ex2.71&2.76. Let $A,B\in M_n(\mathbb C)$, show that

$$\left|\begin{matrix}A&-B\\B&A\end{matrix}\right|=|A+\mathrm{i}B||A-\mathrm{i}B|.$$

Let $C,D\in M_n(\mathbb C)$, if $BC=CB$, show that

$$\left|\begin{matrix}A&B\\C&D\end{matrix}\right|=|AD-CB|.$$

Ex3.18. Let $\alpha_1,\ldots,\alpha_m$ be a set of independent vectors, and $\beta_1,\ldots,\beta_k$ can be expressed as linear combinations of $\alpha_1,\ldots,\alpha_m$ as follows

$$\begin{pmatrix}\beta_1\\\vdots\\\beta_k\end{pmatrix}=A\begin{pmatrix}\alpha_1\\\vdots\\\alpha_m\end{pmatrix},$$

where $A$ is a $k\times m$ matrix. Show that

$$\mathrm{rank}\{\beta_1,\ldots,\beta_k\}=\mathrm{rank}\ A.$$

Ex3.31. Let $\mathbb Q(\sqrt[3]2)=\{a+b\sqrt[3]2+c\sqrt[3]4:a,b,c\in \mathbb Q\}$, show that $\dim_{\mathbb Q}\mathbb Q(\sqrt[3]2)=3$.

Ex.3.91 as knowledge

Ex.3.43

Ex3.45. Let $V=\mathbb R^n[x]$ be the linear space of all polynomials of degree not greater than $n$ over $\mathbb R$. Find the transition matrix from the basis $\{1,x,x^2,\ldots,x^n\}$ to the basis $\{1,(x-a),(x-a)^2,\ldots,(x-a)^n\}$, where $a\in \mathbb R$, through which prove the Taylor formula of polynomial:

$$f(x)=\sum^n_{k=0}\frac{f^{(k)}(a)}{k!}(x-a)^k.$$

Ex9.6.

Ex9.9.

  • Ex.8:13,18,21,29,37,43,44,53,54,58,69,75

  • Ex.10:2,19,25,26,29.

From YCMC & QZC

From DMS