Introduction to Probability

Multivariable Calculus

Algorithms: Part II

Algorithms: Part I

Introduction to Software Design and Architecture

Calculus Two: Sequences and Series

LAFF Linear Algebra

Stanford Machine Learning

Calculus One

Computational Thinking

Effective Thinking Through Mathematics

CS50 Introduction to Computer Science


Week 8 - More on Matrix Inversion

Gauss-Jordan Elimination

  • The key of Gauss-Jordan Elimination is to transfer matrix A to the identity matrix:

  • Ax=bAx=b

  • If A is non-singular, then:

    • A1Ax=xA1b=xx=A1bA^{-1}Ax = x \to A^{-1}b = x \to x = A^{-1}b

Computing A^−1 via Gauss-Jordan Elimination

  • Notice ,α11=1/α11\alpha_{11} = 1 / \alpha_{11}. Every iteration, we scale α11\alpha_{11} to 1.

Cost of inverting a matrix

  • Via Gauss-Jordan, taking advantage of zeroes in the appended identity matrix, requires approximately 2n32n^3 floating point operations.

(Almost) never, ever invert a matrix

  • Solving Ax = b should be accomplished by first computing its LU factorization (possibly with partial pivoting) and then solving with the triangular matrices.

Symmetric Positive Definite(SPD) Matrices

  • Definition: Let ARn×nA \in \mathbb{R}^{n \times n}. Matrix A is said to be symmetric positive definite(SPD) if

    • A is symmetric; and
    • xTAx>0x^T A x > 0 for all nonzero vector xRnx \in \mathbb{R}^n.
  • Consider the quadratic polynomial $$p(\chi) = \alpha \chi^2 + \beta \chi + \gamma = \chi \alpha \chi + \beta \chi + \gamma$$

  • The graph of this function is a parabola that is “concaved up” if α>0\alpha > 0. In that case, it attains a minimum at a unique value χ\chi.

  • Now consider the vector function f:RnRf: \mathbb{R}^n \to \mathbb{R} given by $$f(x) = x^T A x + b^T x + \gamma$$ where ARn×n,bRn, and γRA \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^n, \text{ and } \gamma \in \mathbb{R} are all given. If A is a SPD matrix, then this equation is minimized for a unique vector x. If n=2n = 2, plotting this function when A is SPD yields a paraboloid that is concaved up:

Solving Ax = b when A is Symmetric Positive Definite

Cholesky factorization theorem

  • Let ARn×nA \in \mathbb{R}^{n \times n} be a SPD matrix. Then there exists a lower trianglar matrix LRn×nL \in \mathbb{R}^{n \times n} such that A=LLTA = LL^T. If the diagonal elements of L are chosen to be positive, this factorization is unique.
  • Algorithm:
  • Notice that α11:=α11\alpha_{11} := \sqrt{\alpha_{11} } and a21:=a21/α11a_{21} := a_{21}/\alpha_{11} which are legal if α>0\alpha > 0. It turns out that if A is SPD, then
    • α11>0\alpha_{11} > 0 in the first iteration and hence α11:=α11\alpha_{11} := \sqrt{\alpha_{11} } and a21:=a21/α11a_{21} := a_{21}/\alpha_{11} are legal; and
    • A22:=A22a21a21TA_{22} := A_{22} - a_{21} a_{21}^T is again a SPD matrix.