Linear algebra#

Some notes on linear algebra - basics, matrix calculus, norms, and eigendecompositions. Section numbers refer to Strang's "Linear Algebra and Its Applications".

About this chapter

The linear algebra used across the rest of the book. The first section collects definitions and matrix facts: inner products, determinants, rank, inverses and pseudo-inverses, and the four fundamental subspaces. Matrix calculus follows, with worked gradients of \(a^Tx\), \(x^TAx\) and \(\log\det X\).

The second half is norms and eigenstuff. Eigenvalues come first (Strang 5.1), then the two decompositions: \(A = Q\Lambda Q^T\) for symmetric matrices and the SVD \(X = U\Sigma V^T\) for any matrix. Most of the norms, the condition number and the pseudo-inverse are easiest to read off the singular values, so the SVD section ties the chapter together.

Linear basics#

Definitions used throughout: the trace inner product between matrices, linearity, determinants, independence, and the facts about rank, inverses and subspaces that later sections lean on.

Notation#

  • \(x \preceq y\) - these are vectors and x is less than y elementwise

  • \(X \preceq Y\) - matrices, \(Y-X\) is PSD

    • \(v^TXv \leq v^TYv \:\: \forall v\)

Linearity#

  • inner product \(<X, Y> = \operatorname{tr}(X^TY) = \sum_i \sum_j X_{ij} Y_{ij}\)

    • like inner product if we collapsed into big vector

    • linear

    • symmetric

    • gives angle back

  • linear

    1. superposition \(f(x+y) = f(x)+f(y) \)

    2. proportionality \(f(k\cdot x) = k \cdot f(x)\)

  • bilinear just means a function is linear in 2 variables

  • vector space

    1. closed under addition

    2. contains identity

  • det - sum of products including one element from each row / column with correct sign

    • absolute value = area of parallelogram made by rows (or cols)

    • The rows $(a, b)$ and $(c, d)$ span a parallelogram. Its area is $|ad - bc|$, the absolute value of the determinant.

      Fig. 5 Figure 1. The rows \((a, b)\) and \((c, d)\) span a parallelogram. Its area is \(|ad - bc|\), the absolute value of the determinant.#

  • lin independent: \(c_1x_1+c_2x_2=0 \implies c_1=c_2=0\)

  • cauchy-schwartz inequality: \(\vert x^T y\vert \leq \vert \vert x\vert \vert _2 \vert \vert y\vert \vert \vert _2\)

    • implies triangle inequality: \(\vert \vert x+y\vert \vert ^2 \leq (\vert \vert x\vert \vert + \vert \vert y\vert \vert )^2\)

Matrix properties#

A matrix is invertible exactly when its determinant is nonzero and its null space is just 0. When it isn’t square, the pseudo-inverse takes its place, \(A^\dagger = (A^T A)^{-1} A^T\) when the columns are independent. The range and null space are orthogonal complements, which fixes their dimensions at \(r\) and \(n - r\).

  • \(x^TAx = \operatorname{tr}(xx^TA)\)

  • nonsingular = invertible = nonzero determinant = null space of zero

    • only square matrices

    • rank of mxn matrix- max number of linearly independent columns / rows

      • rank==m==n, then nonsingular

    • ill-conditioned matrix - matrix is close to being singular - very small determinant

  • inverse

    • orthogonal matrix: all columns are orthonormal

      • \(A^{-1} = A^T\)

      • preserves the Euclidean norm \(\vert \vert Ax\vert \vert _2 = \vert \vert x\vert \vert _2\)

    • if diagonal, inverse is invert all elements

    • inverting 3x3 - transpose, find all mini dets, multiply by signs, divide by det

    • psuedo-inverse = Moore-Penrose inverse \(A^\dagger = (A^T A)^{-1} A^T\)

      • if A is nonsingular, \(A^\dagger = A^{-1}\)

      • if rank(A) = m, then must invert using \(A A^T\)

      • if rank(A) = n, then must use \(A^T A\)

    • inversion of matrix is \(\approx O(n^3)\)

    • inverse of psd symmetric matrix is also psd and symmetric

    • if A, B invertible \((AB)^{-1} = B^{-1} A^{-1}\)

  • orthogonal complement - set of orthogonal vectors

    • define R(A) to be range space of A (column space) and N(A) to be null space of A

    • R(A) and N(A) are orthogonal complements

    • dim \(R(A)\) = r

    • dim \(N(A)\) = n-r

    • dim \(R(A^T)\) = r

    • dim \(N(A^T)\) = m-r

  • adjoint - compute with mini-dets

    • \(A^{-1} = adj(A) / \det(A)\)

  • Schur complement of \(X = \begin{bmatrix} A & B \\ C & D\end{bmatrix}\)

    • \(M/D = A - BD^{-1}C\)

    • \(M/A = D-CA^{-1}B\)

    • \(X \succeq 0 \iff M/D \succeq 0\)

Matrix calc#

The trick behind every example below: write out \(f(x + \Delta)\) and keep the part that is linear in \(\Delta\). For scalar functions of a matrix, rewriting a quadratic form as a trace often makes the derivative a one-liner.

  • overview: imagine derivative \(f(x + \Delta)\)

  • function f: \(\text{anything} \to \mathbb{R}^m\)

    • gradient vector \(\nabla_A f(\mathbf{A})\)- partial derivatives with respect to each element of A (vector or matrix)

    • gradient = \(\frac{\partial f}{\partial A}^T\)

  • these next 2 assume numerator layout (numerator-major order, so numerator constant along rows)

  • function f: \(\mathbb{R}^n \to \mathbb{R}^m\)

    • Jacobian matrix: \(\mathbf J = \begin{bmatrix} \dfrac{\partial \mathbf{f}}{\partial x_1} & \cdots & \dfrac{\partial \mathbf{f}}{\partial x_n} \end{bmatrix}= \begin{bmatrix} \dfrac{\partial f_1}{\partial x_1} & \cdots & \dfrac{\partial f_1}{\partial x_n}\\ \vdots & \ddots & \vdots\\ \dfrac{\partial f_m}{\partial x_1} & \cdots & \dfrac{\partial f_m}{\partial x_n} \end{bmatrix}\) - this is dim(f) x dim(x)

  • function f: \(\mathbb{R}^n \to \mathbb{R}\)

    • 2nd derivative is Hessian matrix

      • \(\bold H = \nabla^2 f(x)_{ij} = \frac{\partial^2 f(x)}{\partial x_i \partial x_j} = \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2}\end{bmatrix}\)

  • examples

    • \(\nabla_x a^T x = a\)

    • \(\nabla_x x^TAx = 2Ax\) (if A symmetric, else \((A+A^T)x)\))

    • \(\nabla_x^2 x^TAx = 2A\) (if A symmetric, else \(A+A^T\))

    • \(\nabla_x \log \: \det X = X^{-1}\)

  • we can calculate derivs of quadratic forms by calculating derivs of traces

    • \(x^TAx = \operatorname{tr}[x^TAx] = \operatorname{tr}[xx^TA]\)

    • \(\implies \frac{\partial}{\partial A} x^TAx = \frac{\partial}{\partial A} \operatorname{tr}[xx^TA] = [xx^T]^T = xx^T\)

    • useful result: \(\frac{\partial}{\partial A} \log\vert A\vert = A^{-T}\)

Norms#

Vector norms first, then matrix norms. Several matrix norms are vector norms applied to the singular values: the nuclear norm sums them, the Frobenius norm is their \(L_2\) norm, and the spectral norm is the largest.

  • def

    1. nonnegative

    2. definite f(x) = 0 iff x = 0

    3. proportionality (also called homogenous)

    4. triangle inequality

  • properties

    • convex

Vector norms#

The \(L_p\) norms, the quadratic norm \(\|x\|_P\) defined by a positive definite \(P\), and the dual norm, the largest \(z^T x\) over the unit ball of the original norm. The \(L_1\) and \(L_\infty\) norms are duals of each other and \(L_2\) is its own dual.

  • \(L_p-\)norms: \(\vert \vert x\vert \vert _p = (\sum_{i=1}^n \vert x_i\vert ^p)^{1/p}\)

    • \(L_0\) norm - number of nonzero elements (this is not actually a norm!)

    • \(\vert \vert x\vert \vert _1 = \sum \vert x_i\vert\)

    • \(\vert \vert x\vert \vert _2\) - Euclidean norm

    • \(\vert \vert x\vert \vert _\infty = \max_i \vert x_i\vert\) - also called Cheybyshev norm

  • quadratic norms

    • P-quadratic norm: \(\vert \vert x\vert \vert _P = (x^TPx)^{1/2} = \vert \vert P^{1/2} x \vert \vert _2\) where \(P \in S_{++}^n\)

  • dual norm

    • given a norm \(\vert \vert \cdot \vert \vert\), dual norm \(\vert \vert z\vert \vert _* = \sup\{ z^Tx \: \vert \: \vert \vert x\vert \vert \leq 1\}\)

    • dual of the dual is the original

    • dual of Euclidean is just Euclidean

    • dual of \(l_1\) is \(l_\infty\)

    • dual of spectral norm is some of the singular values

Matrix norms#

  • schatten p-norms: \(\vert \vert X\vert \vert _p = (\sum \sigma^p_i(A) )^{1/p}\) - note this is nice for organization but this p is never really mentioned

    • p=1: nuclear norm = trace norm: \(\vert \vert X\vert \vert _* = \sum_i \sigma_i\)

    • p=2: frobenius norm = euclidean norm: \(\vert \vert X\vert \vert _F^2 = \sqrt {\sum_{ij} X_{ij}^2} = \sqrt{\sum_i \sigma_i^2}\)

    • like vector \(L_2\) norm

    • p=\(\infty\): spectral norm = \(\mathbf{L_2}\)-norm (of a matrix) = \(\vert \vert X\vert \vert _2 = \sigma_\text{max}(X)\)

  • entrywise norms

    • sum-absolute-value norm (like vector \(l_1\))

    • maximum-absolute-value norm (like vector \(l_\infty\))

  • operator norm

    • let \(\vert \vert \cdot\vert \vert _a\) and \(\vert \vert \cdot \vert \vert _b\) be vector norms

    • operator norm \(\vert \vert X\vert \vert _{a,b} = \sup\{ \vert \vert Xu\vert \vert _a \: \vert \: \vert \vert u\vert \vert _b \leq 1 \}\)

      • represents the maximum stretching that X does to a vector u

    • if using p-norms, can get Frobenius and some others

Eigenstuff#

Section numbers follow Strang. For a symmetric matrix the eigenvalues give the determinant (their product), the trace (their sum) and the extremes of \(x^TAx / x^Tx\).

Eigenvalues intro - Strang 5.1#

An eigenvector keeps its direction under \(A\): \(Ax = \lambda x\), so the eigenvalues are the roots of \(\det(A - \lambda I) = 0\). For symmetric matrices they give the determinant, trace, \(L_2\) and Frobenius norms, and positive semi-definite matrices are the symmetric ones with no negative eigenvalues.

Interactive 1. Drag \(v\) and watch \(Av\). Along the blue lines \(Av\) stays on the line through \(v\), so \(Av = \lambda v\) and the length changes by the eigenvalue. The symmetric preset has orthogonal eigenvectors. The rotation has complex eigenvalues \(\pm i\) and turns every \(v\), and the shear has a repeated eigenvalue with only one eigenvector direction (a defective matrix).
  • nice viz

  • elimination changes eigenvalues

  • eigenvector application to diff eqs \(\frac{du}{dt}=Au\)

    • soln is exponential: \(u(t) = c_1 e^{\lambda_1 t} x_1 + c_2 e^{\lambda_2 t} x_2\)

  • eigenvalue eqn: \(Ax = \lambda x \implies (A-\lambda I)x=0\)

    • \(\det(A-\lambda I) = 0\) yields characteristic polynomial

  • eigenvalue properties

    • 0 eigenvalue \(\implies\) A is singular

    • eigenvalues are on the main diagonal when the matrix is triangular

  • expressions when \(A \in \mathbb{S}\)

    • \(\det(A) = \prod_i \lambda_i\)

    • \(\operatorname{tr}(A) = \sum_i \lambda_i\)

    • \(\vert \vert A\vert \vert _2 = \max \vert \lambda_i \vert\)

    • \(\vert \vert A\vert \vert _F = \sqrt{\sum \lambda_i^2}\)

    • \(\lambda_{\max} (A) = \sup_{x \neq 0} \frac{x^T A x}{x^T x}\)

    • \(\lambda_{\min} (A) = \inf_{x \neq 0} \frac{x^T A x}{x^T x}\)

  • defective matrices - lack a full set of eigenvalues

  • positive semi-definite: \(A \in R^{nxn}\)

    • basically these are always symmetric \(A=A^T\)

    • all eigenvalues are nonnegative

    • if \(\forall x \in R^n, x^TAx \geq 0\) then A is positive semi definite (PSD)

      • like it curves up

      • Note: \(x^TAx = \sum_{i, j} x_iA_{i, j} x_j\)

    • if \(\forall x \in R^n, x^TAx > 0\) then A is positive definite (PD)

      • PD \(\to\) full rank, invertible

    • PSD + symmetric \(\implies\) can be written as Gram matrix \(G = X^T X \)

      • if X full rank, then \(G\) is PD

    • PSD notation

      • \(S^n\) - set of symmetric matrices

      • \(S^n_+\) - set of PSD matrices

      • \(S^n_{++}\) - set of PD matrices

Strang 5.2 - diagonalization#

A symmetric matrix factors as \(Q\) \(\Lambda\) \(Q^T\) with orthonormal eigenvectors and the eigenvalues on the diagonal. In that basis powers, inverses and square roots act on each eigenvalue separately.

  • diagonalization = eigenvalue decomposition = spectral decomposition

  • assume A (nxn) is symmetric

    • \(A = \cblue{Q} \corange{\Lambda} \cblue{Q^T}\)

    • Q := eigenvectors as columns, Q is orthonormal

    • \(\Lambda\) := eigenvalues on diagonal

  • only diagonalizable if n independent eigenvectors

    • not related to invertibility

    • eigenvectors corresponding to different eigenvalues are lin. independent

    • other Q matrices won’t produce diagonal

    • there are always n complex eigenvalues

    • orthogonal matrix \(Q^TQ=I\)

  • examples

    • if X, Y symmetric, \(\operatorname{tr}(YX) = \operatorname{tr}(Y \sum \lambda_i q_i q_i^T)\)

    • lets us easily calculate \(A^2\), \(\sqrt{A}\)

    • eigenvalues of \(A^2\) are squared, eigenvectors remain same

    • eigenvalues of \(A^{-1}\) are inverse eigenvalues

    • eigenvalue of rotation matrix is \(i\)

  • eigenvalues for \(AB\) only multiply when A and B share eigenvectors

    • diagonalizable matrices share the same eigenvector matrix S iff \(AB = BA\)

  • generalized eigenvalue decomposition - for 2 symmetric matrices

    • \(A = V \Lambda V^T\), \(B=VV^T\)

Strang 6.3 - singular value decomposition#

Every matrix, square or not, factors into a rotation, a stretch along the axes and another rotation. The stretches are the singular values.

Interactive 2. Set the entries of a 2×2 matrix \(X\) and follow the unit circle through \(V^T\), \(\Sigma\) and \(U\). It ends up as an ellipse whose semi-axes are \(\sigma_1 u_1\) and \(\sigma_2 u_2\). Drag \(X\) toward a singular matrix (for example rows that are multiples of each other): \(\sigma_2\) goes to 0, the ellipse flattens to a line, and the condition number \(\sigma_{\max}/\sigma_{\min}\) blows up.
  • SVD for any nxp matrix: \(X=\cblue{U} \corange{\Sigma} \cgreen{V^T}\)

    • U columns (nxn) are eigenvectors of \(XX^T\)

    • columns of V (pxp) are eigenvectors of \(X^TX\)

    • r singular values on diagonal of \(\corange{\Sigma}\) (nxp) - square roots of nonzero eigenvalues of both \(XX^T\) and \(X^TX\)

    • like rotating, scaling, and rotating back

    • SVD ex. \(A=UDV^T \implies A^{-1} = VD^{-1} U^T\)

    • \(X = \sum_i \sigma_i u_i v_i^T\)

  • properties

    1. for PD matrices, \(\Sigma=\Lambda\), \(U\Sigma V^T = Q \Lambda Q^T\)

    • for other symmetric matrices, any negative eigenvalues in \(\Lambda\) become positive in \(\Sigma\)

  • applications

    • very numerically stable because U and V are orthogonal matrices

    • condition number of invertible nxn matrix = \(\sigma_{\max} / \sigma_{\min}\)

    • \(A=\cblue{U}\corange{\Sigma} \cgreen{V^T} = \cblue{u_1} \corange{\sigma_1} \cgreen{v_1^T} + ... + \cblue{u_r} \corange{\sigma_r} \cgreen{v_r^T}\)

      • we can throw away columns corresponding to small \(\corange{\sigma_i}\)

    • pseudoinverse \(A^+ = V \Sigma^+ U^T\)

Strang 5.3 - difference eqs and power \(A^k\)#

In repeated multiplication \(u_{k+1} = A u_k\), \(A^k\) scales each eigenvector by \(\lambda_i^k\). So the eigenvalue magnitudes decide whether \(u_k\) dies out, stays bounded or blows up, and the largest one eventually dominates, which is the power method.

Interactive 3. Iterating \(u_{k+1} = A u_k\) with eigenvectors \(q_1, q_2\) and eigenvalues \(\lambda_1, \lambda_2\). With both \(\vert\lambda\vert < 1\) the iterates shrink to 0, and with one \(\vert\lambda\vert > 1\) they run off. Either way the direction lines up with the eigenvector of the larger \(\vert\lambda\vert\), at the rate \(\vert\lambda_2/\lambda_1\vert^k\) shown on the right; that is the power method. Set \(\vert\lambda_1\vert = \vert\lambda_2\vert\) and it never settles.
  • compound interest

  • solving for fibonacci numbers

  • Markov matrices

    • steady-state Ax = x

    • corresponds to \(\lambda = 1\)

  • stability of \(u_{k+1} = A u_k\)

    • stable if all eigenvalues satisfy \(\vert \lambda_i\vert\) <1

    • neutrally stable if some \(\vert \lambda_i\vert =1\)

    • unstable if at least one \(\vert \lambda_i\vert\) > 1

  • Leontief’s input-output matrix

  • Perron-Frobenius thm - if A is a positive matrix (positive values), so is its largest eigenvalue and every component of the corresponding eigenvector is also positive

    • useful for ranking, etc.

  • power method: want to find eigenvector \(v\) corresponding to largest eigenvalue

    • \(v = \underset{n \to \infty}{\lim} \frac{A^n v_0}{\vert A^nv_0\vert }\) where \(v_0\) is nonnegative

Key ideas

  • The four fundamental subspaces pair up as orthogonal complements, with dimensions \(r\), \(n - r\), \(r\) and \(m - r\).

  • Matrix gradients come from keeping the part of \(f(x + \Delta)\) linear in \(\Delta\), often after rewriting a quadratic form as a trace.

  • Many matrix norms are vector norms of the singular values, such as nuclear (sum), Frobenius (\(L_2\)) and spectral (max).

  • A symmetric matrix is \(Q \Lambda Q^T\) with orthonormal eigenvectors, and it is PSD exactly when every eigenvalue is nonnegative.

  • Every matrix has an SVD \(U \Sigma V^T\), and the singular values give the condition number \(\sigma_{\max}/\sigma_{\min}\), and terms with small \(\sigma_i\) can be thrown away.

  • In \(u_{k+1} = A u_k\) the eigenvalue magnitudes decide stability, and the power method finds the eigenvector of the largest one.