Determinant

• singular / non-singular

Range & Null

• range(A) : linear comb of cols
• null(A) : \(\{z|Az = 0,z \in R^n \}\)

(Right-)eigenvalue

• Eigenvalue pair: \(Ax=\lambda x\)
• diagonalizable \(n\times n\) matrix are n eigenpairs with \(X=[x_1,\dots, x_n]\) non-singular \(X^{-1}AX\) is a diagonal with eigenvalues on the main diagonal
• Similarity transformation(conjugation): Non-singular matrix \(S\), the matrix \(B=S^{-1}AS\) has the same eigenvalues as \(A\)
  • S is the change of basis matrix
  • A,B are the same linear operator under different basis
  • \(B(S^{-1}x)=\lambda (S^{-1}x)\)

Vector Norms

• definition:
  • \(R^n \rightarrow R\)
  • \(0 \rightarrow 0\)
  • triangle inequality
  • \(|a| \; n(x) = n(ax)\)
• \(l_2\)-norm
• \(l_\inf\)-norm: max
• \(l_1\)-norm
• Matrix-norm: \(||A|| = \max_{||x||=1}||Ax||= \max_{x \neq 0} \frac{||Ax||}{||x||}\)
  • \(||A|| \geq 0; ||A|| = 0 \iff A=0\)
  • \(||A+B|| \leq ||A||+||B||, \forall A,B \in R^{m\times n}\)
  • \(||A \cdot B|| \leq ||A||||B|| \forall A \in R^{m \times n}, B \in R^{n \times l}\)
• \(l_2 = p(\sqrt{A^TA})\)
• \(l_\inf =\) max sum of row
• \(l_1=\) max sum of col

Special matrix class

• Symmetric positive definite matrix
  • Symmetrix : \(A= A^T\)
  • Positive (semi-)definite \(x^*Ax (=)> 0\)
  • Symmetric matrix is positive definite if and only if all its eigenvalues are positive
• non-singular matrix A, \(A^TA\) is positive definite
• Orthogonal matrices
  • columns are pair wise orthonormal(unit)
  • orthogonal vectors: \(u^Tv=0\)
  • \(Q^TQ=I, Q^{-1}=Q^T\)
  • \(||Qx||_2 = ||x||_2\)

Singular value decomposition

• A is a real \(m \times n\), there are orthogonal matrices U,V such that
• \(A=U\Sigma V^T\)
• where \(\Sigma = \left( \begin{array}{cc} S & 0 \\ 0 & 0 \end{array} \right), S = diag\{\sigma_1, \dots , \sigma_r\}\)
• r the rank
• with singular values \(\sigma_i \geq \sigma_{i+1} > 0\)
  • of A, \(\sqrt{\lambda_i}\) of \(B=A^TA\)
  • \(||A||_2 = \sigma_1\) the largest singular value of A
  • Geometric interpretation

Principle component analysis : PCA

1. zero mean, A
2. The largest is \(u_1\)
3. \(B_r = U_r^T A\), first r columns

Solving Linear systems

• Ax=b
• A, nxn real non-singular
• b, n real vector
• x, n real vector

Backward(forward) substitusion

For upper triangular matrix, with all diagonal element non-zero

Gaussian elimination

Transform an arbitrary non-singular matrix into upper(lower) triangular form

Elementary row transformation: * interchange * scale(non-zero) * substraction

LU decomposition

\(Ax=b \rightarrow A=LU\) with L lower triangular, U upper triangular, then forward & backward substitutions

\(M_i\) = gaussian elimination -> with diagonal 1, under one is the coefficient obtained using gaussian elimination.

\(U = (\Pi M_{n-i}) A, L= \Pi M_i^{-1}\)

Compute the determinant by \(det(A)=det(L)det(U)\)

Pivoting

Gaussian elimination with Partial Pivoting(GEPP): When leading term is zero or very close to zero(roundoff error will be magnified), before or during computation. For each iteration, choose the leading term to be the largest term in the column.

Introduce P-matrix for pivoting.

\(U=(\Pi M_i)(\Pi P_i)A\)(for ERT, order doesn’t matter), making \(PA=LU\)

GEPP vectorization

Array operations

Cholesky decomposition

Symmetric positive definite matrix

\(A=LU = LD\tilde{U} = LDL^T = A^T = \tilde{U}^T D L^T\), D is diagonal \(A=LDL^T\), \(G=LD^{1/2}\), \(A=GG^T\)

Sparse Matrix

(i,j,v) pair to denote : a[i,j]=v

LU decomposition for banded matrix

we don’t need to zero out elements that are already zero.

Effect of row/col permutation

Fill-in of A: A with zero elements are replaced by non-zero elements

Arrow matrices : first col/row & diagonal are one.

• Top-left arrow matrix : disasterous fill-in
• Lower-right arrow matrix : no fill-in

Error & condition number

\(x, \hat{x}\) absolute error/relative error with x under(use norm of some kind).

Redisual

\(\hat{y}=b-A\hat{x}\)

Condition number

Assuming that A is non-singular \(\hat{y} =A(x-\hat{x}) \rightarrow x - \hat{x} = A^{-1} \hat{y}\)

\[||x-\hat{x}|| = ||A^{-1}\hat{y}|| \leq ||A^{-1}||\;||\hat{y}||\]

\[\frac1{||x||} \leq \frac{||A||}{||b||}\]

We then have

\[\frac{||x-\hat{x}||}{||x||} \leq ||A|| \; ||A^{-1}|| \frac{||\hat{y}||}{||b||} = \kappa(A)\frac{||\hat{y}||}{||b||}\]

• 1 means good conditioned: Idealy conditioned
• \(\inf\) is bad: singular

About condition number:

• \(\kappa(A) \geq 1 : ||A|| \; ||A^{-1}|| \geq ||AA^{-1}||\)
• \(\kappa(\alpha A) = \kappa(A)\)
• Some intuition:
  • \(\kappa(A) = \max(\frac{RE_out}{RE_in})\) for matrix A
  • \(\kappa_2(A) = \frac{||A||}{||E||}\) where E is the smallest purturabtion needed for \(A+E\) to be singular
• note that determinant is not a measurement of nunsingularity
  • non-singular matrices can have small det; almost-singular matrix can have “normal” determinant
• orthogonal matrix Q, \(\kappa_2(Q) = 1\)
  • \(||Qx||_2 = 1\) if \(||x||_2 = 1\), we have \(||Q||_2 = 1\)
• symmetric positive definite matrix A:
  • \(\kappa_2(A) = \frac{\lambda_1}{\lambda_n}\), the largest divide by the smallest
  • \(||A||_2 = \lambda_1\)
  • the inverse of A is also symmetric positive definite matrix with eigenvalues \(\frac1{\lambda_i}\)
• Almost singular -> ill-conditioned
• Hilbert matrix -> ill-conditioned