Cramer Method for Linear Systems

Solving Linear Systems

Cramer's rule solves a linear system directly from determinants when its coefficient matrix is invertible.

It expresses each solution component as $a ratio of two determinants$ . For large systems, Gaussian elimination requires much less computation.

Adjugate Matrix

The $adjugate matrix$ connects the determinant to both the inverse formula and Cramer's rule.

Here $adjugate$ means the transpose of the cofactor matrix. It is a different construction from the conjugate transpose of a complex matrix.

For matrix $A \in \mathbb{R}^{n \times n}$ , the adjugate matrix is defined as:

\tilde{A} = (\tilde{a}_{ij})_{i=1,\ldots,n \atop j=1,\ldots,n} \in \mathbb{R}^{n \times n}

Each entry of the adjugate matrix is given by

\tilde{a}_{ij} = (-1)^{i+j} \cdot \det A_{ji}

Here, $A_{ji}$ is the submatrix formed by deleting row $j$ and column $i$ from $A$ . The indices are swapped because the cofactors occupy transposed positions in the adjugate.

The adjugate matrix $\tilde{A}$ contains the $cofactors$ of $A$ in transposed positions.

Structure of the Adjugate Matrix

Write each minor determinant as $c_{ij}$ . The alternating signs and $transposed indices$ remain visible in the whole adjugate:

c_{ij}=\det A_{ij}

Each element is calculated by taking the determinant of the corresponding submatrix, then given a sign based on the checkerboard pattern $(-1)^{i+j}$ .

Adjugate Matrix Identity

The adjugate satisfies the $following identity$ with the original matrix:

\begin{aligned} &A \cdot \tilde{A} \\ &= \tilde{A} \cdot A \\ &= \begin{pmatrix} \det A & 0 & \cdots & 0 \\ 0 & \det A & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \det A \end{pmatrix} \end{aligned}

In other words:

A \cdot \tilde{A} = (\det A) \cdot I

A diagonal entry of the product is a $Laplace expansion along the same row$ , so it equals the determinant. An off-diagonal entry uses a different row. That expansion is the determinant of a matrix with two equal rows, so it is zero.

Matrix Inverse Formula

From this identity, we can derive the $matrix inverse formula$ using the adjugate matrix.

If matrix $A \in \mathbb{R}^{n \times n}$ is invertible, then:

A^{-1} = \frac{1}{\det A} \cdot \tilde{A}

However, calculating the matrix inverse with this formula is much less efficient than Gaussian elimination for large matrices.

Example for a Two by Two Matrix

For a $2\times2$ matrix:

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}

Its determinant is:

\det A = a \cdot d - b \cdot c

Its adjugate is:

\tilde{A} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

So its inverse is:

A^{-1} = \frac{1}{a \cdot d - b \cdot c} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

Compute each entry of the $numerator matrix$ :

\begin{aligned} &m_{11}=a\cdot d-b\cdot c \\ &m_{12}=-a\cdot b+a\cdot b \\ &m_{21}=c\cdot d-c\cdot d \\ &m_{22}=-c\cdot b+a\cdot d \end{aligned}

Solving a Linear System with Determinants

Let $A \in \mathbb{R}^{n \times n}$ be an invertible matrix and $a^1, a^2, \ldots, a^n \in \mathbb{R}^n$ be the columns of $A$ . For vector $b \in \mathbb{R}^n$ , the solution $x \in \mathbb{R}^n$ of the linear equation system $A \cdot x = b$ is given by:

Write $A_j(b)$ for the matrix with column $j$ replaced by $b$ :

A_j(b)=(a^1\;\ldots\;a^{j-1}\;b\;a^{j+1}\;\ldots\;a^n)

Cramer's formula applies for $j = 1, 2, \ldots, n$ .

To calculate the $j$ -th component of solution $x$ , we $replace the$ $j$ -th column of matrix $A$ with vector $b$ , then calculate the determinant of this modified matrix and divide it by the determinant of the original matrix $A$ .

Proving the Solution Formula

The proof of Cramer's rule uses $Laplace expansion$ and the adjugate identity.

For $j = 1, \ldots, n$ :

\begin{aligned} x_j &= (A^{-1} \cdot b)_j \\ &= \sum_{i=1}^{n} (A^{-1})_{ji} \cdot b_i \\ &= \sum_{i=1}^{n} \frac{1}{\det A} \cdot \tilde{a}_{ji} \cdot b_i \end{aligned}

= \frac{1}{\det A} \sum_{i=1}^{n} (-1)^{i+j} \cdot \det A_{ij} \cdot b_i

The final equality follows from Laplace expansion along the $j$ -th column.

Solving a Three Variable System by Determinants

Solve the following system by replacing $one column$ of $A$ at a time:

\begin{aligned} &A = \begin{pmatrix} 1 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 1 \end{pmatrix}, \\ &b = \begin{pmatrix} 20 \\ 40 \\ 30 \end{pmatrix} \end{aligned}

Calculate the determinant of $A$ .

\begin{aligned} \det A &= 1 \cdot ((-1) \cdot 1 - 1 \cdot 1) \\ &\quad{}- 1 \cdot (1 \cdot 1 - (-1) \cdot 1) \\ &\quad{}+ (-1) \cdot (1 \cdot 1 - (-1) \cdot (-1)) \\ &=-4 \end{aligned}

The calculation gives $\det A=-4$ , so the determinant is nonzero. Thus $A$ is invertible and the system has a unique solution. We can now apply Cramer's rule:

\begin{aligned} x_1 &= \frac{1}{\det A} \cdot \det \begin{pmatrix} 20 & 1 & -1 \\ 40 & -1 & 1 \\ 30 & 1 & 1 \end{pmatrix} \\ &= \frac{-120}{-4} \\ &= 30 \end{aligned}

\begin{aligned} x_2 &= \frac{1}{\det A} \cdot \det \begin{pmatrix} 1 & 20 & -1 \\ 1 & 40 & 1 \\ -1 & 30 & 1 \end{pmatrix} \\ &= \frac{-100}{-4} \\ &= 25 \end{aligned}

\begin{aligned} x_3 &= \frac{1}{\det A} \cdot \det \begin{pmatrix} 1 & 1 & 20 \\ 1 & -1 & 40 \\ -1 & 1 & 30 \end{pmatrix} \\ &= \frac{-140}{-4} \\ &= 35 \end{aligned}

Check the three numerator determinants by expanding their first rows. Then substitute the solution into each original equation.

\det A_1(b)=-40-10-70=-120

Solution Properties for Integer Matrices

If $A \in \mathbb{Z}^{n \times n}$ is invertible and $b \in \mathbb{Z}^n$ , then the entries of $A^{-1}$ and the solution $x$ of $A \cdot x = b$ $are rational$ . Before reduction, they can all be written over the common denominator $|\det A|$ . Each reduced denominator therefore divides $|\det A|$ .

This occurs because determinant calculation only involves addition, subtraction, and multiplication operations, so the determinant of an integer matrix is always an integer. In the inverse formula and Cramer's rule, the only division operation is division by $\det A$ .