Cramer's Rule

This is a method for finding a Matrix Inverse and for solving a System of Linear Equations.


Finding Inverse

The formula is $A^{-1} = \cfrac{1}{| A |} C^T$


$2 \times 2$ case: Motivation

Let $A$ be an $2 \times 2$ matrix

  • $A = \begin{bmatrix}

a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix}$

  • let's find $A^{-1}$ with Gauss-Jordan elimination (see Inverse Matrices)
    • $\left[ \begin{array}{cc|cc}

a_{11} & a_{12} & 1 & 0 \\ a_{21} & a_{22} & 0 & 1 \\ \end{array} \right] \sim $ row 2: $\text{row $2$} - \cfrac{a_{21}}{a_{11}} \text{row $1$}$

    • $\sim \left[ \begin{array}{cc|cc}

a_{11} & a_{12} & 1 & 0 \\ 0 & a_{22} - a_{12} \cfrac{a_{21}}{a_{11}} & - \cfrac{a_{21}}{a_{11}} & 1 \\ \end{array} \right] \sim $ now divide first row by $a_{11}$ and multiply second by $a_{11}$

    • $\sim \left[ \begin{array}{cc|cc}

1 & \cfrac{a_{12}}{a_{11}} & \cfrac{1}{a_{11}} & 0 \\ 0 & a_{11} a_{22} - a_{12} a_{21} & - a_{21} & a_{11} \\ \end{array} \right] =$ now note that $a_{11} a_{22} - a_{12} a_{21} = | A |$, so

    • $ = \left[ \begin{array}{cc|cc}

1 & \cfrac{a_{12}}{a_{11}} & \cfrac{1}{a_{11}} & 0 \\ 0 & |A| & - a_{21} & a_{11} \\ \end{array} \right] \sim $ let's divide row 2 by $|A|$

    • $ \sim \left[ \begin{array}{cc|cc}

1 & \cfrac{a_{12}}{a_{11}} & \cfrac{1}{a_{11}} & 0 \\ 0 & 1 & - \cfrac{a_{21}}{|A|} & \cfrac{a_{11}}{|A|} \\ \end{array} \right] \sim $ now for row 1: $\text{row $1$} - \cfrac{a_{12}}{a_{11}} \text{row $2$}$

    • $ \sim \left[ \begin{array}{cc|cc}

1 & 0 & \cfrac{a_{22}}{|A|} & - \cfrac{a_{12}}{|A|} \\ 0 & 1 & - \cfrac{a_{21}}{|A|} & \cfrac{a_{11}}{|A|} \\ \end{array} \right]$

  • so $A^{-1} = \cfrac{1}{|A|} \begin{bmatrix}

a_{22} & - a_{12} \\ - a_{21} & a_{11} \\ \end{bmatrix}$

  • now we can note that the Cofactors of $A$ are: $C_{11} = a_{22}, C_{12} = -a_{21}, C_{21} = - a_{12}, C_{22} = a_{11}$
  • we can put all cofactors in one matrix $C = \begin{bmatrix}

C_{11} & C_{12} \\ C_{21} & C_{22} \\ \end{bmatrix} = \begin{bmatrix} a_{22} & -a_{21} \\ -a_{12} & a_{11} \\ \end{bmatrix} = \begin{bmatrix} a_{22} & - a_{12} \\ - a_{21} & a_{11} \\ \end{bmatrix}^T$

  • this is the same as in the formula for $A^{-1}$, but transposed!
  • so $A^{-1} = \cfrac{1}{| A |} C^T$


General Case: Check

Does it always work? Let's check

  • if $A^{-1} = \cfrac{1}{| A |} C^T$, then $A \, C^T = |A| \, I$
  • or, $\underbrace{\begin{bmatrix}
 a_{11} & a_{12} & \cdots & a_{1n} \\
 a_{21} & a_{22} & \cdots & a_{2n} \\
 \vdots & \vdots & \ddots & \vdots \\
 a_{n1} & a_{n2} & \cdots & a_{nn} \\

\end{bmatrix}}_{A} \underbrace{\begin{bmatrix}

 C_{11} & C_{21} & \cdots & C_{n1} \\
 C_{12} & C_{22} & \cdots & C_{n2} \\
 \vdots & \vdots & \ddots & \vdots \\
 C_{1n} & C_{2n} & \cdots & C_{nn} \\

\end{bmatrix}}_{C^T} = \underbrace{\begin{bmatrix}

 |A| & 0 & \cdots & 0 \\
 0 & |A| & \cdots & 0 \\
 \vdots & \vdots & \ddots & \vdots \\
 0 & 0 & \cdots & |A| \\

\end{bmatrix}}_{|A| \, I}$

  • so why do we have zeros off the diagonal?
    • $\begin{bmatrix}

a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix} \begin{bmatrix} C_{11} & C_{21} \\ C_{12} & C_{22} \\ \end{bmatrix} = \begin{bmatrix} \boxed{a_{11} C_{11}} + a_{12} C_{12} & a_{11} C_{21} + a_{12} C_{22} \\ a_{21} C_{11} + a_{22} C_{12} & a_{21} C_{21} + \boxed{a_{22} C_{22}} \\ \end{bmatrix}$

    • need to check that $\text{row $i$} \times \text{cofactor of $i$} = |A|$
    • and $\text{row $i$} \times \text{cofactors of $j$} = 0$ ($i \ne j$)
    • then we'll have $|A|$ only on the diagonal


$\text{row $i$} \times \text{cofactors of $i$} = |A|$

  • $\text{row $i$} = \begin{bmatrix} a_{i1} & a_{i2} & \cdots & a_{in} \end{bmatrix}$
  • $\text{cofactors of $i$} = \begin{bmatrix} C_{i1} \\ C_{i2} \\ \vdots \\ C_{in} \end{bmatrix}$
  • so $\text{row $i$} \times \text{cofactors of $i$} = \sum\limits_k a_{ik} C_{ik}$
  • note that this is the Cofactors formula for calculating the determinant!
  • thus, $\text{row $i$} \times \text{cofactors of $i$} = |A|$


$\text{row $i$} \times \text{cofactors of $j$} = 0$ for $i \ne j$

  • let's have a look what this dot product calculates
  • take row $i$ of $A$ and row $j$ of $C$ (i.e. column $j$ of $C^T$)
  • $\text{row $i$} \times \text{cofactors of $j$} = \begin{bmatrix} a_{i1} & a_{i2} & \cdots & a_{in} \end{bmatrix} \begin{bmatrix} C_{j1} \\ C_{j2} \\ \vdots \\ C_{jn} \end{bmatrix} = \sum\limits_k a_{ik} C_{jk}$
  • this is a cofactors formula for a new matrix $A^*$ where the row $i$ of $A$ is copied to row $j$ of $A$. So this new matrix has two equal rows, therefore $| A^* | = 0$
  • and thus, $\text{row $i$} \times \text{cofactors of $j$} = 0$


so we showed that

  • $A \, C^T = |A| \, I$
  • therefore, $A^{-1} = \cfrac{1}{| A |} C^T$


Cramer's Rule: Solving $A \mathbf x = \mathbf b$

Now since we can find the inverse of $A^{-1}$, we can solve the system $A \mathbf x = \mathbf b$

  • let $A$ be $n \times n$ invertible matrix
  • we know that $A^{-1} = \cfrac{1}{|A|} C^T$, so $\mathbf x = A^{-1} \mathbf b = \cfrac{1}{|A|} C^T \mathbf b$
  • let's have a look at the components of $\mathbf x$
    • $x_1 = \cfrac{ (C^T \mathbf b)_1 }{|A|}$ (where $(C^T \mathbf b)_1$ is the 1st element of this vector)
    • $(C^T \mathbf b)_1 = (\text{column 1 of $C$})^T \mathbf b = C_{11} b_1 + C_{21} b_2 + \ ... $
    • any time we multiply something by cofactors, it's the same as getting a determinant of some matrix
    • in this case, we're calculating the determinant of $B_1$ - matrix $A$ with column 1 replaced with $\mathbf b$
    • thus, $x_1 = \cfrac{|B_1|}{|A|} = \begin{vmatrix}
 b_{1} & a_{12} & \cdots & a_{1n} \\
 b_{2} & a_{22} & \cdots & a_{2n} \\
 \vdots & \vdots & \ddots & \vdots \\
 b_{n} & a_{n2} & \cdots & a_{nn} \\

\end{vmatrix} / \begin{vmatrix}

 a_{11} & a_{12} & \cdots & a_{1n} \\
 a_{21} & a_{22} & \cdots & a_{2n} \\
 \vdots & \vdots & \ddots & \vdots \\
 a_{n1} & a_{n2} & \cdots & a_{nn} \\

\end{vmatrix}$

  • and generally, $x_i = \cfrac{|B_i|}{|A|}$, where $B_i$ is $A$ with column $i$ replaced by $\mathbf b$

This is known as the Cramer's Rule


Efficiency

This is known as not very practical method for computing the inverse or for solving the system


Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion