2 Basic Notation
The following A\in\mathbb{K}^{m\times n}, with \mathbb{K}=\mathbb{R} or \mathbb{C}. For square plates A\in\mathbb{K}^{n\times n}:
A^T=\text{transpose},\qquad A^*=\overline{A}^{\,T}=\text{conjugate transpose}. In the real field A^*=A^T.
\mathop{\mathrm{spec}}(A)=\{\lambda\in\mathbb{C}:\det(A-\lambda I)=0\}, \qquad \rho(A)=\max_{\lambda\in\mathop{\mathrm{spec}}(A)}|\lambda|.
3 Summary Table
| Type | Defining condition | Eigenvalues | Key properties |
|---|---|---|---|
| Diagonal | a_{ij}=0 for i\neq j | diagonal elements | diagonal inverse if not singular |
| Scale | A=\alpha I | all equal to \alpha | switch with every matrix |
| Triangular | a_{ij}=0 above or below the diagonal | diagonal elements | \det A=\prod_i a_{ii} |
| Real symmetric | A^T=A | real | diagonally orthogonally |
| Real antisymmetrical | A^T=-A | pure imaginary or 0 | diagonal nothing |
| Hermitian | A^*=A | real | unitarily diagonalizable |
| Antihermitiana | A^*=-A | pure imaginary or 0 | iA Hermitian |
| Orthogonal | A^TA=I | \vert \lambda\vert =1 | A^{-1}=A^T, \det A=\pm1 |
| Unitarian | A^*A=I | \vert \lambda\vert =1 | A^{-1}=A^* |
| Normal | A^*A=AA^* | complexes in general | unitarily diagonalizable |
| SPD | A=A^T, x^TAx>0 | positive | Cholesky, invertible |
| SPSD | A=A^T, x^TAx\ge0 | nonnegative | Gram, square root |
| negative definite | A=A^T, x^TAx<0 | negative | -A SPD |
| Indefinite | square shape of variable sign | positive and negative | not semidefinite |
| Idempotent | A^2=A | 0,1 | projector, \mathop{\mathrm{rank}}A=\mathop{\mathrm{tr}}A |
| Involution | A^2=I | \pm1 | A^{-1}=A |
| Nilpotent | A^k=0 | only 0 | \det A=0 |
| Permutation | one unit per line/column | roots of unity | orthogonal |
| Householder | H=I-2vv^T/(v^Tv) | \pm1 | symmetric and orthogonal |
| Toeplitz | a_{ij}=t_{i-j} | — | constant diagonals |
| Hankel | a_{ij}=h_{i+j} | — | constant antidiagonal |
| Circulating | rows obtained for cyclic shift | DFT of coefficients | diagonalized by DFT |
| Vandermonde | V_{ij}=x_i^{j-1} | — | known instrument |
| Companion | associated with a polynomial | roots of polynomial | norm matrix for polynomials |
| Stocha | elements \ge0, row/column sums =1 | contains \lambda=1 | \rho(A)=1 |
| Gram Matrix | G=B^*B | nonnegative | positive semidefinite Hermitian |
4 Inner Products
4.1 Real Inner Product
A product to scale up \mathbb{R}^n is a function \langle x,y\rangle that satisfies:
bilinearity;
symmetry;
positivity:
\langle x,x\rangle\ge0;
- defined:
\langle x,x\rangle=0 \iff x=0.
Product euclide inner:
\langle x,y\rangle=x^Ty.
4.2 Complex Inner Product
Up \mathbb{C}^n:
\langle x,y\rangle=x^*y.
Property:
\langle x,y\rangle = \overline{\langle y,x\rangle}.
4.3 Weighted Inner Product
M=M^*\succ0, then \langle x,y\rangle_M=x^*My.
The associated norm is:
\|x\|_M=\sqrt{x^*Mx}.
5 Vector Norms
A vector rule meets:
\|x\|\ge0, \|x\|=0\iff x=0, \|\alpha x\|=|\alpha|\,\|x\|, \|x+y\|\le\|x\|+\|y\|.
5.1 1-Norm
\|x\|_1=\sum_{i=1}^n|x_i|.
5.2 2-Norm
\|x\|_2= \sqrt{\sum_{i=1}^n|x_i|^2} = \sqrt{x^*x}.
5.3 Infinity Norm
\|x\|_\infty=\max_i|x_i|.
5.4 p-Norm
For 1\le p<\infty: \|x\|_p= \left( \sum_i|x_i|^p \right)^{1/p}.
5.5 Cauchy–Schwarz Inequality
For norms induced by scalar product:
|\langle x,y\rangle| \le \|x\|\,\|y\|.
5.6 Equivalence of Norms in Finite Dimensions
Up \mathbb{K}^n all norms are equivalent.
In particular:
\|x\|_\infty \le \|x\|_2 \le \sqrt n\,\|x\|_\infty, \|x\|_2 \le \|x\|_1 \le \sqrt n\,\|x\|_2.
6 Matrix Norms
A matrix norm meets the properties of a norm on the matrix space.
A matrix rule is submultiplicative if:
\|AB\| \le \|A\|\,\|B\|.
6.1 Induced Matrix Norm
Date a vector rule:
\|A\| = \max_{x\neq0} \frac{\|Ax\|}{\|x\|} = \max_{\|x\|=1}\|Ax\|.
Induced norms are automatically compatible with the vector norm: \|Ax\| \le \|A\|\,\|x\|.
6.2 Matrix 1-Norm
\|A\|_1 = \max_j \sum_i|a_{ij}|.
It is the maximum of the sum of the absolute values along the columns.
6.3 Matrix Infinity Norm
\|A\|_\infty = \max_i \sum_j|a_{ij}|.
It is the maximum of the sum of the absolute values along the rows.
6.4 Matrix 2-Norm
\|A\|_2 = \sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^*A)}.
A is normal:
\|A\|_2 = \rho(A).
A is symmetric/Hermitian:
\|A\|_2 = \max_i|\lambda_i|.
6.5 Frobenius Norm
\|A\|_F = \sqrt{ \sum_{i,j}|a_{ij}|^2 }.
Equivalently:
\|A\|_F = \sqrt{\mathop{\mathrm{tr}}(A^*A)} = \sqrt{ \sum_i\sigma_i^2 }.
Property:
\|A\|_2 \le \|A\|_F \le \sqrt{\mathop{\mathrm{rank}}(A)}\,\|A\|_2.
Frobenius is not a norm induced by a vector norm, but is submultiplicative:
\|AB\|_F \le \|A\|_F\|B\|_F.
In addition:
\|AB\|_F \le \|A\|_2\|B\|_F, \|AB\|_F \le \|A\|_F\|B\|_2.
7 Compatibility between Norms
A matrix norm \|\cdot\|_M is compatible with a vector rule \|\cdot\|_v if:
\|Ax\|_v \le \|A\|_M\|x\|_v.
Any induced matrix rule is compatible with the vector norm from which it is induced.
For norm norms:
\|Ax\|_1 \le \|A\|_1\|x\|_1, \|Ax\|_2 \le \|A\|_2\|x\|_2, \|Ax\|_\infty \le \|A\|_\infty\|x\|_\infty.
8 Norms and Inner Products
Each inner product induces a norm:
\|x\| = \sqrt{\langle x,x\rangle}.
Not every norm is induced by a scalar product.
A norm is induced by a scalar product if and only if it meets the identity of the parallelogram:
\|x+y\|^2+\|x-y\|^2 = 2\|x\|^2+2\|y\|^2.
For the Euclidean rule:
\|x\|_2=\sqrt{x^*x}.
For a positive SPD/Hermitian matrix M:
\|x\|_M=\sqrt{x^*Mx}.
9 Dual, Frobenius, and Unitarily Invariant Norms
The dual rule is ’ \|y\|_*=\max_{\|x\|\le1}|y^*x|.
1/p+1/q=1: (\|\cdot\|_p)^*=\|\cdot\|_q, \qquad |x^*y|\le\|x\|_p\|y\|_q. Frobenius inner product \langle A,B\rangle_F=\mathop{\mathrm{tr}}(A^*B), \qquad \|A\|_F=\sqrt{\mathop{\mathrm{tr}}(A^*A)}. For U,V Units: \|UAV\|_2=\|A\|_2,\qquad \|UAV\|_F=\|A\|_F. Schatten rules: \|A\|_{S_p}=\left(\sum_i\sigma_i^p\right)^{1/p}. Nuclear norms: \|A\|_*=\sum_i\sigma_i.
10 Fundamental Subspaces and Rank
Both A\in\mathbb{K}^{m\times n} and \mathop{\mathrm{rank}}(A)=r. The four basic subspaces are \mathop{\mathrm{range}}(A)\subseteq\mathbb{K}^m,\qquad \ker(A)\subseteq\mathbb{K}^n, \mathop{\mathrm{range}}(A^*)\subseteq\mathbb{K}^n,\qquad \ker(A^*)\subseteq\mathbb{K}^m. The size is \dim\mathop{\mathrm{range}}(A)=\dim\mathop{\mathrm{range}}(A^*)=r, \quad \dim\ker(A)=n-r, \quad \dim\ker(A^*)=m-r. Theorem rank–nulled’: \mathop{\mathrm{rank}}(A)+\dim\ker(A)=n. Basic orthogonal relations: \mathop{\mathrm{range}}(A)^\perp=\ker(A^*),\qquad \mathop{\mathrm{range}}(A^*)^\perp=\ker(A), \mathbb{K}^m=\mathop{\mathrm{range}}(A)\oplus\ker(A^*),\qquad \mathbb{K}^n=\mathop{\mathrm{range}}(A^*)\oplus\ker(A).
11 Rank and Invertibility: Equivalent Conditions
For A\in\mathbb{K}^{n\times n} are equivalent:
\begin{align*} &A\text{ invertible},\\ &\mathop{\mathrm{rank}}(A)=n,\\ &\det(A)\neq0,\\ &0\notin\mathop{\mathrm{spec}}(A),\\ &\ker(A)=\{0\},\\ &Ax=0\Rightarrow x=0,\\ &\text{the columns of }A\text{ are linearly independent},\\ &\text{the rows of }A\text{ are linearly independent}. \end{align*}
12 Rectangular Matrices
12.1 Full-Rank Matrix
For A\in\mathbb{K}^{m\times n}: \mathop{\mathrm{rank}}(A)=\min(m,n).
m\ge n and \mathop{\mathrm{rank}}(A)=n, A has full rank for columns.
m\le n and \mathop{\mathrm{rank}}(A)=m, A has full rank for rows.
12.2 Matrix with Orthonormal Columns
Q^*Q=I.
Q is rectangular, in general:
QQ^*\neq I.
QQ^* is the orthogonal projector on \mathop{\mathrm{range}}(Q).
12.3 Matrix with Orthonormal Rows
QQ^*=I. In this case Q^*Q He's an orthogonal projector.
13 Basic Properties of the Determinant, Trace, and Spectrum
For A,B\in\mathbb{K}^{n\times n}:
\det(AB)=\det(A)\det(B), \det(A^T)=\det(A), \qquad \det(A^*)=\overline{\det(A)}, \det(A^{-1})=\frac{1}{\det A}, \mathop{\mathrm{tr}}(AB)=\mathop{\mathrm{tr}}(BA), \mathop{\mathrm{tr}}(A)=\sum_{i=1}^n\lambda_i, \det(A)=\prod_{i=1}^n\lambda_i, where the eigenvalues are counted with a multiplicity of algebraic.
B=S^{-1}AS, then A and B are similar and have:
same characteristic polynomial;
same eigenvalues;
itself decisive;
same trace;
same rank.
14 Eigenvalues, Spectrum, and Spectral Radius
Av=\lambda v,\qquad v e0, \qquad p_A(\lambda)=\det(\lambda I-A). For each eigenvalue: 1\le m_g(\lambda)\le m_a(\lambda). Useful transformations: \mathop{\mathrm{spec}}(A^{-1})=\{\lambda^{-1}:\lambda\in\mathop{\mathrm{spec}}(A)\}, \quad \mathop{\mathrm{spec}}(A+\alpha I)=\mathop{\mathrm{spec}}(A)+\alpha, \mathop{\mathrm{spec}}(\alpha A)=\alpha\mathop{\mathrm{spec}}(A),\qquad \mathop{\mathrm{spec}}(A^k)=\{\lambda^k:\lambda\in\mathop{\mathrm{spec}}(A)\}. For each polynomial p: \mathop{\mathrm{spec}}(p(A))=p(\mathop{\mathrm{spec}}(A)). The spectral radius is \rho(A)=\max_{\lambda\in\mathop{\mathrm{spec}}(A)}|\lambda|. For each induced matrix rule:
\rho(A)\le\|A\|. Gelfand formula: \rho(A)=\lim_{k\to\infty}\|A^k\|^{1/k}. In finite dimensions: A^k\to0\iff\rho(A)<1.
14.1 Gershgorin’s Theorem
\mathop{\mathrm{spec}}(A)\subseteq\bigcup_i \left\{z\in\mathbb{C}:|z-a_{ii}|\le\sum_{j e i}|a_{ij}|\right\}.
15 Spectral Theorem and Rayleigh Quotient
For A=A^*: A=U\Lambda U^*,\qquad \Lambda\in\mathbb{R}^{n\times n}. In the symmetric real case:
A=Q\Lambda Q^T. Rayleigh quotient is R_A(x)=\frac{x^*Ax}{x^*x}. For A=A^*: \lambda_{\min}\le R_A(x)\le\lambda_{\max}, \lambda_{\min}=\min_{x e0}R_A(x),\qquad \lambda_{\max}=\max_{x e0}R_A(x). Ordering \lambda_1\le\cdots\le\lambda_n Courant–Fischer provides \lambda_k=\min_{\dim S=k}\max_{0 e x\in S}R_A(x) =\max_{\dim S=n-k+1}\min_{0 e x\in S}R_A(x).
16 Diagonalizability and Canonical Forms
16.1 Diagonalizable Matrix
A is diagonalized if there is an invertible matrix V such that A=V\Lambda V^{-1}, with \Lambda diagonal.
Equival to the existence of a base constituted by motorists.
Sufficient conditions:
A he has n distinct eigenvalues;
A is normal on \mathbb{C};
A is real symmetric.
16.2 Defective Matrix
A non- diagonalized matrix is called defective. For at least one eigenvalue:
\dim\ker(A-\lambda I) < \text{algebraic multiplicity of }\lambda.
16.3 Jordan Form
Each complex matrix is similar to a block matrix: A=VJV^{-1}, where J consists of Jordan blocks J_k(\lambda)= \begin{pmatrix} \lambda&1&&\\ &\lambda&\ddots&\\ &&\ddots&1\\ &&&\lambda \end{pmatrix}.
17 Schur Decomposition
For each A\in\mathbb{C}^{n\times n}:
A=QTQ^*, with Q unitary and T superior triangular. The diagonal elements of T are the eigenvalues of A. In the real case there is a form of real Schur with diagonal blocks 1\times1 and 2\times2. A is normal, T is diagonal. Schur's form is numerically stable; Jordan's form is mainly theoretical.
18 Elementary and Structured Matrices
18.1 Zero Matrix
A=0. Property:
\mathop{\mathrm{rank}}(A)=0.
\mathop{\mathrm{spec}}(A)=\{0\}.
A is nilpotent, symmetric/Hermitian, normal and semidefinite positive and negative.
18.2 Identity Matrix
I_n=\mathop{\mathrm{diag}}(1,\dots,1). Property:
I_nA=AI_n=A.
I_n^{-1}=I_n.
\mathop{\mathrm{spec}}(I_n)=\{1\}.
It is diagonal, symmetric, Hermitian, orthogonal, unitary, normal, SPD.
18.3 Diagonal Matrix
D=\mathop{\mathrm{diag}}(d_1,\dots,d_n). Property:
\mathop{\mathrm{spec}}(D)=\{d_1,\dots,d_n\}.
\det D=\prod_i d_i.
\mathop{\mathrm{rank}}D= number of diagonal elements not null.
D is invertible if and only if d_i\neq0 for each i.
In this case D^{-1}=\mathop{\mathrm{diag}}(d_1^{-1},\dots,d_n^{-1}).
18.4 Scalar Matrix
A=\alpha I. Property:
switched with each square matrix of the same size;
\mathop{\mathrm{spec}}(A)=\{\alpha\};
\det A=\alpha^n;
is invertible if and only if \alpha\neq0.
18.5 Upper and Lower Triangular Matrices
Upper triangular:
a_{ij}=0\qquad i>j. Lower triangular: a_{ij}=0\qquad i<j. Property:
\det A=\prod_i a_{ii}.
The eigenvalues are the diagonal elements.
It is invertible if and only if a_{ii}\neq0 for each i.
The inverse of a not singular triangular is triangular of the same type.
The triangular matrix product of the same type is triangular.
18.6 Strictly Triangular Matrix
Triangular with diagonal nothing. Property:
is nilpotent;
A^n=0 for a matrix n\times n;
All eigenvalues are null.
18.7 Bidiagonal Matrix
It has elements not null only on the main diagonal and on a diagonal immediately adjacent.
18.8 Tridiagonal Matrix
a_{ij}=0\qquad |i-j|>1. Property:
tridiagonal linear systems can be solved in O(n) operations;
if symmetric, it is completely described by the main diagonal and an adjacent diagonal.
18.9 Band Matrix
Ha. a_{ij}=0 \qquad\text{for}\qquad i-j>p \quad\text{or}\quad j-i>q.
pandq are the lower and upper band semi-ampies.
18.10 Hessenberg Matrix
Upper Hessenberg:
a_{ij}=0\qquad i>j+1. Lower Hessenberg: a_{ij}=0\qquad j>i+1. Each square matrix can be reduced by unit/orthogonal similarities in the shape of Hessenberg.
18.11 Block Matrix
A= \begin{pmatrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{pmatrix}. The usual matrix operations apply to blocks when the dimensions are compatible.
A_{11} is invertible, Schur's complement is S=A_{22}-A_{21}A_{11}^{-1}A_{12}.
19 Symmetry, Adjoints, and Normality
19.1 Real Symmetric Matrix
A^T=A. Property:
all eigenvalues are real;
autovectors related to separate autovalves are orthogonal;
exists an orthogonal matrix Q such that A=Q\Lambda Q^T;
is always diagonalized;
\|A\|_2=\rho(A)=\max_i|\lambda_i|.
19.2 Real Skew-Symmetric Matrix
A^T=-A. Property:
a_{ii}=0;
eigenvalues are null or pure imaginary;
if n is odd, \det A=0;
x^TAx=0 for each x\in\mathbb{R}^n.
19.3 Hermitian Matrix
A^*=A. Property:
real eigenvalues;
autovectors associated with distinct eigenvalues are orthogonal;
exist U such that A=U\Lambda U^*, \qquad \Lambda\in\mathbb{R}^{n\times n}.
19.4 Skew-Hermitian Matrix
A^*=-A. Property:
eigenvalues are pure or null imaginary;
iA is Hermitian;
e^A is unitary.
19.5 Normal Matrix
A^*A=AA^*. Fundamental equivalences:
A is normal if and only if it is diagonally diagonally;
exist U such that A=U\Lambda U^*.
They're normal.
hermitiane matrices;
antihermitiane;
unit;
real symmetries;
real orthogonals.
20 Orthogonal and Unitary Matrices
20.1 Orthogonal Matrix
Q^TQ=QQ^T=I. Property:
Q^{-1}=Q^T;
preserves scalable product, angles and Euclidean norm: \|Qx\|_2=\|x\|_2;
|\lambda_i|=1;
\det Q=\pm1;
\mathop{\mathrm{cond}}_2(Q)=1.
20.2 Unitary Matrix
U^*U=UU^*=I. Property:
U^{-1}=U^*;
preserves hermitian product;
\|Ux\|_2=\|x\|_2;
|\lambda_i|=1;
|\det U|=1.
20.3 Rotation Matrix
In \mathbb{R}^2:
R(\theta)= \begin{pmatrix} \cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix}. Property:
R^TR=I,\qquad \det R=1.
20.4 Householder Reflection
For v\neq0:
H=I-2\frac{vv^T}{v^Tv}. Property:
H^T=H;
H^TH=I;
H^{-1}=H;
H^2=I;
\det H=-1;
eigenvalues: -1 in the direction of v, +1 in the orthogonal subspace.
20.5 Givens Rotation
It acts not banally on two coordinates:
G= \begin{pmatrix} 1&&&&\\ &c&&-s&\\ &&1&&\\ &s&&c&\\ &&&&1 \end{pmatrix}, \qquad c^2+s^2=1. It is orthogonal and is used to selectively cancel elements of a matrix.
21 Definiteness
21.1 Positive Definite Matrix
For a symmetric real matrix:
A\succ0 \quad\Longleftrightarrow\quad x^TAx>0 \quad\forall x\neq0. Equivalent properties:
all eigenvalues are positive;
exists the factorization of Cholesky A=LL^T with L lower triangular and positive diagonal;
all major minors”leading”are positive (Sylvester crime);
A=B^TB with B invertable;
A^{-1}\succ0.
In addition:
\det A>0.
21.2 Positive Semidefinite Matrix
A\succeq0 \quad\Longleftrightarrow\quad x^TAx\ge0 \quad\forall x. Property:
non-negative eigenvalues;
exist B such that A=B^TB;
admits a positive symmetric square root:
A^{1/2}A^{1/2}=A.
21.3 Negative Definite Matrix
A\prec0 \quad\Longleftrightarrow\quad x^TAx<0 \quad\forall x\neq0. Equival to -A\succ0. eigenvalues are all negative.
21.4 Negative Semidefinite Matrix
A\preceq0 \quad\Longleftrightarrow\quad x^TAx\le0. eigenvalues are not positive.
21.5 Indefinite Matrix
There are x,y\neq0 such as x^TAx>0, \qquad y^TAy<0. For a symmetric matrix this is equivalent to the presence of at least one positive eigenvalue and at least one negative.
22 Matrices Defined by Algebraic Equations
22.1 Idempotent Matrix
P^2=P. Property:
eigenvalues in \{0,1\};
is diagonalized;
\mathop{\mathrm{rank}}P=\mathop{\mathrm{tr}}P;
represents a projection.
22.2 Orthogonal Projector
P^2=P, \qquad P^T=P. Property:
P project orthogonally on \mathop{\mathrm{range}}(P);
\mathbb{R}^n=\mathop{\mathrm{range}}(P)\oplus\ker(P);
\|P\|_2=1 if P\neq0.
A has linearly independent columns:
P=A(A^TA)^{-1}A^T is the orthogonal projector on \mathop{\mathrm{range}}(A).
22.3 Oblique Projector
P^2=P, \qquad P^T\neq P. The projection takes place along a subspace not necessarily orthogonal to the image subspace.
22.4 Involutory Matrix
A^2=I. Property:
A^{-1}=A;
eigenvalues in \{-1,1\};
is diagonalized on different characteristic fields from 2.
22.5 Nilpotent Matrix
Existing k\ge1 such that A^k=0. Property:
only eigenvalue: 0;
\det A=0;
\mathop{\mathrm{tr}}A=0;
I-A is always invertible;
if A^k=0:
(I-A)^{-1}=I+A+\cdots+A^{k-1}.
22.6 Unipotent Matrix
A=I+N, with N nilpotent. All eigenvalues of A are equal to 1.
23 Permutation and Sparse Matrices
23.1 Permutation Matrix
It is obtained by switching rows or columns I. Property:
contains exactly one 1 in each row and column;
P^{-1}=P^T;
is orthogonal;
\det P=\pm1;
multiply to the left permutate rows, to the right permutate columns.
23.2 Sparse Matrix
A matrix is called scattered when the number of nonzero elements is much lower than mn. The notion is computational, not algebraic.
23.3 Diagonally Dominant Matrix
Dominance by rows:
|a_{ii}| \ge \sum_{j\neq i}|a_{ij}|. Directly dominant:
|a_{ii}| > \sum_{j\neq i}|a_{ij}|. A strictly diagonally dominant matrix is not singular.
24 Classical Special Matrices
24.1 Gram Matrix
For carriers v_1,\dots,v_n:
G_{ij}=\langle v_i,v_j\rangle. Equivalently: G=V^*V. Property:
G is Hermitian;
G\succeq0;
G\succ0 if and only if the carriers are linearly independent;
\mathop{\mathrm{rank}}(G)=\mathop{\mathrm{rank}}(V).
24.2 Vandermonde Matrix
V= \begin{pmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{pmatrix}. determinant:
\det V= \prod_{1\le i<j\le n}(x_j-x_i). It is invertible if and only if x_i They're distinct.
24.3 Toeplitz Matrix
a_{ij}=t_{i-j}. The elements are constant along each diagonal.
Shape:
T= \begin{pmatrix} t_0&t_{-1}&t_{-2}&\cdots\\ t_1&t_0&t_{-1}&\cdots\\ t_2&t_1&t_0&\cdots\\ \vdots&\vdots&\vdots&\ddots \end{pmatrix}.
24.4 Hankel Matrix
a_{ij}=h_{i+j}. The elements are constant along the antidiagonals.
24.5 Circulant Matrix
C= \begin{pmatrix} c_0&c_{n-1}&\cdots&c_1\\ c_1&c_0&\cdots&c_2\\ \vdots&&\ddots&\vdots\\ c_{n-1}&c_{n-2}&\cdots&c_0 \end{pmatrix}. Property:
is diagonalized by Fourier's discreet matrix;
eigenvalues are the DFT of the carrier (c_0,\dots,c_{n-1});
all circular matrices of the same size switch between them.
24.6 Companion Matrix
For monic polynomial p(\lambda)= \lambda^n+a_{n-1}\lambda^{n-1}+\cdots+a_1\lambda+a_0, a common convention C= \begin{pmatrix} 0&0&\cdots&0&-a_0\\ 1&0&\cdots&0&-a_1\\ 0&1&\cdots&0&-a_2\\ \vdots&&\ddots&\vdots&\vdots\\ 0&0&\cdots&1&-a_{n-1} \end{pmatrix}. The polynomial characteristic of C It is p.
24.7 Cauchy Matrix
C_{ij}=\frac{1}{x_i+y_j}, when x_i+y_j\neq0. It has explicit formulas for determinant and inverse and is often very numerically ill-conditioned.
24.8 Hilbert Matrix
H_{ij}=\frac{1}{i+j-1}. Property:
symmetric;
positive definition;
strongly badly conditioned for n growing.
25 Nonnegative and Stochastic Matrices
25.1 Nonnegative Matrix
A\ge0 means a_{ij}\ge0 \quad\forall i,j. Inequality is a component.
25.2 Positive Matrix
A>0 means a_{ij}>0 \quad\forall i,j. Not to be confused with”definita positiva”.
25.3 Row-Stochastic Matrix
a_{ij}\ge0, \qquad \sum_j a_{ij}=1. Property:
A\mathbf{1}=\mathbf{1};
1 is eigenvalue;
\rho(A)=1.
25.4 Column-Stochastic Matrix
a_{ij}\ge0, \qquad \sum_i a_{ij}=1. Then \mathbf{1}^TA=\mathbf{1}^T.
25.5 Doubly Stochastic Matrix
It is stochastic for both rows and columns. Every permutation matrix is bistocastic.
26 Matrix Classes Used in Numerical Analysis
26.1 Z-Matrix
A real matrix A is a Z- Matrix if a_{ij}\le0 \qquad i\neq j.
26.2 M-Matrix
One M-matrix can be represented as A=sI-B, \qquad B\ge0, \qquad s\ge\rho(B). s>\rho(B), is a M- Not unusual matrix.
For one M- not singular matrix:
A^{-1}\ge0;
eigenvalues have a positive real part;
A is a Z- Matrix.
26.3 P-Matrix
A square real matrix is a P-Matrix if all its major minors are positive.
Property:
every SPD matrix is a P-matrix;
I'll give you the P- matrices have a central role in the problems of linear complementarity.
26.4 Monotone Matrix
A not singular real matrix A is called monotonous if A^{-1}\ge0.
26.5 Irreducible Matrix
A square matrix is reducible if there is a permutation matrix P such that P^TAP= \begin{pmatrix} A_{11}&A_{12}\\ 0&A_{22} \end{pmatrix}. Otherwise it is irreducible.
27 Important Relationships between Matrix Classes
\boxed{ A\text{ SPD} \Longrightarrow A\text{ symmetric} \Longrightarrow A\text{ normal} \Longrightarrow A\text{ diagonalizable} }
\boxed{ A\text{ Hermitian} \Longrightarrow A\text{ normal} \Longrightarrow A\text{ unitarily diagonalizable} }
\boxed{ A\text{ unitary} \Longrightarrow A\text{ normal} }
\boxed{ A\text{ orthogonal} \Longrightarrow A\text{ normal} }
\boxed{ A^2=A \Longrightarrow \mathop{\mathrm{spec}}(A)\subseteq\{0,1\} }
\boxed{ A^2=I \Longrightarrow \mathop{\mathrm{spec}}(A)\subseteq\{-1,1\} }
\boxed{ A^k=0 \Longrightarrow \mathop{\mathrm{spec}}(A)=\{0\} }
\boxed{ A=B^*B \Longrightarrow A\succeq0 }
\boxed{ A=B^*B,\ \mathop{\mathrm{rank}}(B)=n \Longrightarrow A\succ0 }
28 Appendix: Terminology Not to Confuse
- matrix positiva:
a_{ij}>0. It is an element property by element.
- matrix definita positiva:
x^TAx>0 \quad\forall x\neq0. It is a property of the square form.
- matrix ortogonale:
Q^TQ=I. Doesn't mean the matrix elements are”ortogonali”: rows and columns are orthonormal.
matrix diagonalizzabiledoes not necessarily mean symmetric.
matrix simmetricareal is always diagonalized orthogonally.
matrix normaleit is always diagonally, but it is not necessarily Hermitian.
Semidefinita positivadoes not imply invertability.
Strettamente diagonalmente dominanteimplies invertability, but not necessarily positive definiteness.
29 Block Matrices and the Schur Complement
Both M=\begin{pmatrix}A&B\\C&D\end{pmatrix}. For a diagonal block matrix:
\det\begin{pmatrix}A&0\\0&D\end{pmatrix}=\det A\det D, \qquad \begin{pmatrix}A&0\\0&D\end{pmatrix}^{-1} =\begin{pmatrix}A^{-1}&0\\0&D^{-1}\end{pmatrix}.
A is invertible, Schur complement A and S_D=D-CA^{-1}B. Yes. M= \begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix} \begin{pmatrix}A&B\\0&S_D\end{pmatrix}, \qquad \det M=\det A\det S_D.
AandS_D are invertible: M^{-1}=\begin{pmatrix} A^{-1}+A^{-1}BS_D^{-1}CA^{-1}&-A^{-1}BS_D^{-1}\\ -S_D^{-1}CA^{-1}&S_D^{-1} \end{pmatrix}. For M=M^*: M=\begin{pmatrix}A&B\\B^*&D\end{pmatrix},\quad A\succ0, M\succ0\iff D-B^*A^{-1}B\succ0. System block removal M(x,y)^T=(f,g)^T produces S_Dy=g-CA^{-1}f,\qquad Ax=f-By.
29.1 Saddle-Point and KKT Matrices
K=\begin{pmatrix}H&A^*\\A&0\end{pmatrix}.
H=H^*,K is Hermitian but generally indefinite. H\succ0 and A has full rank for rows, K is not unusual. Schur’s complement is’ S=-AH^{-1}A^*\prec0.
30 LU Factorization of Rectangular Matrices
Both A\in\mathbb{K}^{m\times n}.
30.1 LU without Pivoting
When gaussiane eliminations can be performed without row exchanges, a rectangular matrix admits a factorization of the type A=LU.
m\ge n:
L\in\mathbb{K}^{m\times n}, \qquad U\in\mathbb{K}^{n\times n}, with L bottom trapezoidal and U superior triangular.
m\le n:
L\in\mathbb{K}^{m\times m}, \qquad U\in\mathbb{K}^{m\times n}, with L lower triangular and U Top trapezoidal.
30.2 LU with Partial Pivoting
The norm form is PA=LU, where P is a matrix of permutation of the rows.
For rectangular plates:
the partial pivoting exchange rows;
the factorization proceeds up to \min(m,n) steps;
the numerical rank can emerge from the presence of small or null pivot.
30.3 LU with Full Pivoting
Factorization with full pivoting is PAQ=LU, where:
P permutes the rows;
Q permutes the columns.
At each step you choose as a pivot the maximum module element in the subblock still not factorized.
Advantages:
greater robustness than partial pivoting;
useful to reveal the rank.
Disadvantages
higher cost in search of pivot;
more permutations.
30.4 Rank-Revealing Form with Full Pivoting
\mathop{\mathrm{rank}}(A)=r, after appropriate permutations:
PAQ= \begin{pmatrix} L_{11}\\ L_{21} \end{pmatrix} \begin{pmatrix} U_{11} & U_{12} \end{pmatrix}, where L_{11}\in\mathbb{K}^{r\times r}, \qquad U_{11}\in\mathbb{K}^{r\times r} They are not singular.
31 Elementary Frobenius Matrices for LU
An elementary Frobenius matrix associated with Gaussian elimination has the shape F_k=I-\ell_k e_k^T, where \ell_k contains the multipliers used to undo the items under the column pivot k.
For example:
F_k= \begin{pmatrix} 1&&&&\\ &\ddots&&&\\ &&1&&\\ &&-\ell_{k+1,k}&1&\\ &&\vdots&&\ddots\\ &&-\ell_{n,k}&&&1 \end{pmatrix}.
Property:
F_k is lower triangular;
\det(F_k)=1;
F_k is invertible;
F_k^{-1}=I+\ell_k e_k^T.
Gaussian elimination can be written as U=F_{n-1}\cdots F_2F_1A.
So:
A=LU, \qquad L=F_1^{-1}F_2^{-1}\cdots F_{n-1}^{-1}.
With pivoting:
PA=LU.
32 LDL^* Factorization
For hermitiane machines:
A=LDL^*. For indefinite matrices, symmetric pivoting is used:
P^*AP=LDL^*, with D diagonal blocks, typically with blocks 1\times1 and 2\times2. In the real case: P^TAP=LDL^T. It is particularly suitable for indefinite symmetric systems and KKT.
33 QR Factorization of Rectangular Matrices
Both A\in\mathbb{K}^{m\times n}.
33.1 Tall Matrix: m\ge n
A has full rank for columns:
\mathop{\mathrm{rank}}(A)=n.
Reduced QR:
A=QR, with Q\in\mathbb{K}^{m\times n}, \qquad Q^*Q=I_n, and R\in\mathbb{K}^{n\times n} superior and not singular triangular.
Full QR:
A=\widehat Q \begin{pmatrix} R\\ 0 \end{pmatrix}, where \widehat Q\in\mathbb{K}^{m\times m} is unitary/orthagonal.
33.2 Wide Matrix: m\le n
A norm QR produces:
A=QR, with Q\in\mathbb{K}^{m\times m}, \qquad R\in\mathbb{K}^{m\times n}, where R is superior trapezoidal.
A has full rank for rows:
\mathop{\mathrm{rank}}(A)=m.
33.3 QR with Column Pivoting
The shape is AP=QR, where P is a matrix of permutation of the columns.
It is used for:
improve stability;
reveal the rank;
deal with problems at the least squares-deficient.
\mathop{\mathrm{rank}}(A)=r, ideally:
AP= Q \begin{pmatrix} R_{11} & R_{12}\\ 0 & 0 \end{pmatrix}, with R_{11}\in\mathbb{K}^{r\times r} not singular.
34 LQ, RRQR, and COD Factorizations
34.1 LQ Factorization
For A\in\mathbb{K}^{m\times n} with m\le n:
A=LQ.
A has full rank for rows, in reduced form L\in\mathbb{K}^{m\times m} is not unusual and lower triangular Q_1Q_1^*=I_m. LQ gets by applying QR to A^*.
34.2 Rank-Revealing QR
AP=QR=Q\begin{pmatrix}R_{11}&R_{12}\\0&R_{22}\end{pmatrix}. For numerical rank r, good RRQR makes R_{11}\in\mathbb{K}^{r\times r} well conditioned and R_{22} Baby.
34.3 Complete Orthogonal Decomposition
For \mathop{\mathrm{rank}}(A)=r: A=Q\begin{pmatrix}T&0\\0&0\end{pmatrix}Z^*, with Q,Z Units and T\in\mathbb{K}^{r\times r} triangular not singular. It is useful for numerical rank, least squares-deficient and minimum-norm solutions.
35 SVD: Forms and Advanced Properties
Both A\in\mathbb{K}^{m\times n}, \mathop{\mathrm{rank}}(A)=r. Complete SVD:
A=U\Sigma V^*. SVD compact:
A=U_r\Sigma_rV_r^*,\qquad \Sigma_r=\mathop{\mathrm{diag}}(\sigma_1,\dots,\sigma_r),\quad \sigma_r>0. From SVD: \mathop{\mathrm{range}}(A)=\operatorname{span}(u_1,\dots,u_r),\qquad \ker(A^*)=\operatorname{span}(u_{r+1},\dots,u_m), \mathop{\mathrm{range}}(A^*)=\operatorname{span}(v_1,\dots,v_r),\qquad \ker(A)=\operatorname{span}(v_{r+1},\dots,v_n). The pseudoinverse is A^\dagger=V_r\Sigma_r^{-1}U_r^*.
35.1 Eckart–Young–Mirsky Theorem
For k<r:
A_k=U_k\Sigma_kV_k^* is a better approximation of rank to the most «k, with \|A-A_k\|_2=\sigma_{k+1},\qquad \|A-A_k\|_F=\left(\sum_{j=k+1}^r\sigma_j^2\right)^{1/2}.
36 Table of Main Factorizations
| Factorization | matrix | Form | Use |
|---|---|---|---|
| L | General | PAQ=LU | systems, elimination, rank |
| Cholesky | SPD/HPD | A=LL^* | positive defined systems |
| LDL^* | Hermitian | P^*AP=LDL^* | indefinite, KKT |
| QR | above all m\ge n | A=QR | least squares |
| L | above all m\le n | A=LQ | minimum-norm |
| RRQR | General | AP=QR | numerical rank |
| COD | General | A=Q\begin{psmallmatrix}T&0\\0&0\end{psmallmatrix}Z^* | deficient rank |
| SVD | General | A=U\Sigma V^* | rank, pseudoinverse, LS |
| Schur | square | A=QTQ^* | eigenvalues |
| Jordan | square | A=VJV^{-1} | theory |
37 Generalized Inverses and the Pseudoinverse
37.1 Left Inverse
For A\in\mathbb{K}^{m\times n}, \qquad m\ge n, a matrix L\in\mathbb{K}^{n\times m} is a left inverse if LA=I_n.
It exists if and only if:
\mathop{\mathrm{rank}}(A)=n.
A canonical choice:
L=(A^*A)^{-1}A^*.
37.2 Right Inverse
For A\in\mathbb{K}^{m\times n}, \qquad m\le n, a matrix R\in\mathbb{K}^{n\times m} is a right inverse if AR=I_m.
It exists if and only if:
\mathop{\mathrm{rank}}(A)=m.
A canonical choice:
R=A^*(AA^*)^{-1}.
37.3 Generalized Inverse
A matrix G is a generalized inverse of A if AGA=A.
In general it is not unique.
37.4 Moore–Penrose Pseudoinverse
Moore’s pseudoinverse–Penrose A\in\mathbb{K}^{m\times n} is the only matrix A^\dagger\in\mathbb{K}^{n\times m} that satisfies: AA^\dagger A=A, A^\dagger AA^\dagger=A^\dagger, (AA^\dagger)^*=AA^\dagger, (A^\dagger A)^*=A^\dagger A.
Minimum Properties
For every b\in\mathbb{K}^m, the vector
x^\dagger=A^\dagger b
is the unique minimum-Euclidean-norm least-squares solution:
x^\dagger =\mathop{\mathrm{argmin}}_{x} \left\{\|x\|_2: x\in\mathop{\mathrm{argmin}}_{z}\|Az-b\|_2\right\}.
In particular, if Ax=b is consistent, then A^\dagger b is the unique solution of minimum norm. Moreover,
AA^\dagger b =\mathop{\mathrm{argmin}}_{y\in\mathop{\mathrm{range}}(A)} \|b-y\|_2,
and the minimum residual is orthogonal to the range of A:
b-AA^\dagger b\in\ker(A^*).
Among all generalized inverses G satisfying AGA=A, the Moore–Penrose pseudoinverse is the unique one with minimum Frobenius norm:
A^\dagger =\mathop{\mathrm{argmin}}_{G:\,AGA=A}\|G\|_F.
If A has full row rank, A^\dagger is the minimum-Frobenius-norm right inverse; if A has full column rank, it is the minimum-Frobenius-norm left inverse.
37.5 Pseudoinverse via the SVD
A=U\Sigma V^*, then A^\dagger=V\Sigma^\dagger U^*, where \Sigma^\dagger you get inverting only the singular values not null.
\Sigma=\mathop{\mathrm{diag}}(\sigma_1,\dots,\sigma_r,0,\dots), then \Sigma^\dagger= \mathop{\mathrm{diag}}\left( \frac1{\sigma_1}, \dots, \frac1{\sigma_r}, 0,\dots \right) with the transposed dimensions.
37.6 Pseudoinverse via Two QR Factorizations
Let A\in\mathbb{K}^{m\times n} have rank r. First compute a rank-revealing QR factorization with column pivoting and retain only the nonzero part:
A\Pi=Q_1R,
where Q_1\in\mathbb{K}^{m\times r} has orthonormal columns and R\in\mathbb{K}^{r\times n} has full row rank. Then compute a thin QR factorization of R^*:
R^*=ZT,
where Z\in\mathbb{K}^{n\times r} has orthonormal columns and T\in\mathbb{K}^{r\times r} is nonsingular and upper triangular. Since R=T^*Z^*,
R^\dagger=ZT^{-*},
and therefore
\boxed{A^\dagger=\Pi ZT^{-*}Q_1^*.}
No inverse needs to be formed explicitly: solve the triangular system
T^*Y=Q_1^*
and assemble A^\dagger=\Pi ZY. Thus a general rank-r pseudoinverse can be computed with two QR factorizations and triangular solves, without forming the normal equations.
37.7 Special Cases
A is square and invertible:
A^\dagger=A^{-1}.
A has full rank for columns:
A^\dagger=(A^*A)^{-1}A^*.
A has full rank for rows:
A^\dagger=A^*(AA^*)^{-1}.
37.8 Projectors Associated with the Pseudoinverse
AA^\dagger is the orthogonal projector on \mathop{\mathrm{range}}(A).
A^\dagger A is the orthogonal projector on \mathop{\mathrm{range}}(A^*)=(\ker A)^\perp.
I-AA^\dagger is the orthogonal projector on \ker(A^*).
I-A^\dagger A is the orthogonal projector on \ker(A).
37.9 Least Squares and the Pseudoinverse
The minimum norm solution of the problem \min_x\|Ax-b\|_2 is: x^\dagger=A^\dagger b.
All solutions at the smallest squares are: x=A^\dagger b+(I-A^\dagger A)z, \qquad z\in\mathbb{K}^n.
The minimum residue is:
r_\star=b-AA^\dagger b.
Projection b up \mathop{\mathrm{range}}(A) is:
AA^\dagger b.
38 Pseudoinverse: Identities and Decompositions
In addition to Moore–Penrose conditions:
(A^\dagger)^\dagger=A,\qquad (A^*)^\dagger=(A^\dagger)^*, \mathop{\mathrm{range}}(A^\dagger)=\mathop{\mathrm{range}}(A^*),\qquad \ker(A^\dagger)=\ker(A^*). In general:
(AB)^\dagger e B^\dagger A^\dagger. The matrices AA^\dagger,\qquad A^\dagger A are respectively the orthogonal projectors on \mathop{\mathrm{range}}(A) and \mathop{\mathrm{range}}(A^*).
39 Least-Squares Problems
Both A\in\mathbb{K}^{m\times n}, \qquad b\in\mathbb{K}^m.
The problem at the least squares is \min_{x\in\mathbb{K}^n}\|Ax-b\|_2.
39.1 Normal Equations
Every solution to the least squares meets:
A^*(Ax-b)=0, i.e. A^*Ax=A^*b.
Geometric interpretation:
Ax is the orthogonal projection of b up \mathop{\mathrm{range}}(A).
39.2 Tall Full-Column-Rank Case
m\ge n, \qquad \mathop{\mathrm{rank}}(A)=n, the solution to the least squares is unique:
x=(A^*A)^{-1}A^*b.
Using reduced QR:
A=QR, you have Rx=Q^*b.
39.3 Tall Rank-Deficient Case
m\ge n, \qquad \mathop{\mathrm{rank}}(A)=r<n, solutions to the least squares are not in general unique.
The whole of the solutions is close:
x=x_0+z, \qquad z\in\ker(A).
Among all the solutions to the least squares there is a single minimum Euclidean norm solution:
x^\dagger=A^\dagger b.
39.4 Wide Full-Row-Rank Case
m<n, \qquad \mathop{\mathrm{rank}}(A)=m, the system Ax=b is compatible for each b.
There are endless solutions.
The minimum norm solution is:
x^\dagger=A^*(AA^*)^{-1}b.
39.5 Wide Rank-Deficient Case
m<n, \qquad \mathop{\mathrm{rank}}(A)=r<m, the system can be incompatible.
You search:
\min_x \|Ax-b\|_2.
The minimum norm solution between all solutions at the least squares is:
x^\dagger=A^\dagger b.
39.6 Characterization of Least-Squares Solutions
x_\star is solution to the least squares if and only if: A^*(Ax_\star-b)=0.
Equivalently:
b-Ax_\star\perp\mathop{\mathrm{range}}(A).
39.7 Numerical Choice of Method
A has full rank for columns, normal equations meet \kappa_2(A^*A)=\\kappa_2(A)^2. QR avoids the conditioning square due to the formation of A^*A; SVD and COD are particularly indicated in rank-deficient issues. For full row and natural matrices use LQ or QR A^*.
40 Condition Number
For an invertible square matrix:
\mathop{\mathrm{cond}}_p(A) = \|A\|_p\|A^{-1}\|_p.
norm 2:
\mathop{\mathrm{cond}}_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}.
For a full-scale rectangular matrix:
\mathop{\mathrm{cond}}_2(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}, where \sigma_{\min} is the smallest not null singular value.
In terms of pseudoinverse:
\mathop{\mathrm{cond}}_2(A) = \|A\|_2\|A^\dagger\|_2.
For an orthogonal/unitarian matrix:
\mathop{\mathrm{cond}}_2(A)=1.
41 Perturbations, Residuals, and Numerical Stability
For Ax=b, A not singular:
\kappa(A)=\|A\|\,\|A^{-1}\|. If it is disturbed only b:
\frac{\|\delta x\|}{\|x\|} \le \kappa(A)\frac{\|\delta b\|}{\|b\|}. The residue of an approximate solution \widehat x and r=b-A\widehat x. A small residue does not necessarily imply small forward error if A is bad condition. The backward error measures the minimum disruption of data for which \widehat x is an exact solution. Conditioning is a property of the problem; stability is a property of the algorithm.