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 Full Rank
- Smith normal form.
- Act on a non-zero vector.
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.
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.
Matrix Function
Jordan Canonical Form
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} As a corollary, we have the expansion of determinant along a row or column and raise the inductive definition of determinant. 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)$, thenCauchy-Binet Formula
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_1It 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<\cdotsVandermonde 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 iWe 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 j多项式的整性 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
- 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)$.
- 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)$.
- If exchanging the $i$-th and $j$-th columns of $A$ gives $B$, then $f(A)=-f(B)$.
- $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
Space
Symmetric Space
Skew-Symmetric Space
Ex2.5
Act on Basis
Act on basis
Representation of Matrix
Root Space
The geometric multiplicity of an eigenvalue $\lambda$ is the dimension of the eigenspace $E_\lambda=\{v\in V|Av=\lambda v\}$,
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.
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 iEx1.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).$$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$.
From YCMC & QZC
From DMS
谢的练习题跳过