Command Palette

Search for a command to run...

Solving Linear Systems

Cramer's rule is a method for solving systems of linear equations using determinants. This method provides a direct way to calculate solutions of linear equation systems when the coefficient matrix is invertible.

This method is very useful for understanding the relationship between determinants and solutions of linear systems, although it is computationally less efficient compared to Gaussian elimination for large systems.

Complementary Matrix

Before discussing Cramer's rule, we need to understand the concept of complementary matrix which forms the basis of this method.

For matrix ARn×nA \in \mathbb{R}^{n \times n}, the complementary matrix is defined as:

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

with elements:

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

Note that the indices in AjiA_{ji} are swapped (not AijA_{ij}).

The complementary matrix A~\tilde{A} is a matrix consisting of cofactors of matrix AA, but with transposed positions.

Structure of Complementary Matrix

The complementary matrix has the following structure:

A~=(detA11detA21detA31detA12detA22detA32detA13detA23detA33)\tilde{A} = \begin{pmatrix} \det A_{11} & -\det A_{21} & \det A_{31} & \cdots \\ -\det A_{12} & \det A_{22} & -\det A_{32} & \cdots \\ \det A_{13} & -\det A_{23} & \det A_{33} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}

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

Fundamental Properties of Complementary Matrix

One of the most important properties of the complementary matrix is its relationship with the original matrix:

AA~=A~A=(detA000detA000detA)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}

In other words:

AA~=(detA)IA \cdot \tilde{A} = (\det A) \cdot I

This property is very important because it provides a direct relationship between the matrix, its complementary matrix, and its determinant.

Matrix Inverse Formula

From the fundamental property above, we can derive the matrix inverse formula using the complementary matrix.

If matrix ARn×nA \in \mathbb{R}^{n \times n} is invertible, then:

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

However, calculating matrix inverse using this formula is much less efficient compared to Gaussian elimination for large matrices.

Example for 2×2 Matrix

For matrix n=2n = 2:

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

Its determinant is:

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

Its complementary matrix is:

A~=(dbca)\tilde{A} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

So its inverse is:

A1=1adbc(dbca)A^{-1} = \frac{1}{a \cdot d - b \cdot c} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}

We can verify that:

AA1=1adbc(adbcab+abcdcdcb+ad)A \cdot A^{-1} = \frac{1}{a \cdot d - b \cdot c} \begin{pmatrix} a \cdot d - b \cdot c & -a \cdot b + a \cdot b \\ c \cdot d - c \cdot d & -c \cdot b + a \cdot d \end{pmatrix}
=(1001)=I= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I

Theorem Statement

Now we can formulate Cramer's rule for solving systems of linear equations.

Let ARn×nA \in \mathbb{R}^{n \times n} be an invertible matrix and a1,a2,,anRna^1, a^2, \ldots, a^n \in \mathbb{R}^n be the columns of AA. For vector bRnb \in \mathbb{R}^n, the solution xRnx \in \mathbb{R}^n of the linear equation system Ax=bA \cdot x = b is given by:

xj=det(a1    aj1  b  aj+1    an)detAx_j = \frac{\det(a^1 \; \ldots \; a^{j-1} \; b \; a^{j+1} \; \ldots \; a^n)}{\det A}

for j=1,2,,nj = 1, 2, \ldots, n.

To calculate the jj-th component of solution xx, we replace the jj-th column of matrix AA with vector bb, then calculate the determinant of this modified matrix and divide it by the determinant of the original matrix AA.

Proof Using Laplace Expansion

The proof of Cramer's rule uses Laplace expansion and properties of the complementary matrix.

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

xj=(A1b)j=i=1n(A1)jibi=i=1n1detAa~jibix_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
=1detAi=1n(1)i+jdetAijbi= \frac{1}{\det A} \sum_{i=1}^{n} (-1)^{i+j} \cdot \det A_{ij} \cdot b_i
=1detAdet(a1    aj1  b  aj+1    an)= \frac{1}{\det A} \cdot \det(a^1 \; \ldots \; a^{j-1} \; b \; a^{j+1} \; \ldots \; a^n)

based on Laplace expansion with respect to the jj-th column.

Application Example

Let's look at a concrete example of applying Cramer's rule:

A=(111111111),b=(204030)A = \begin{pmatrix} 1 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 20 \\ 40 \\ 30 \end{pmatrix}

Since:

detA=1((1)111)1(11(1)1)\det A = 1 \cdot ((-1) \cdot 1 - 1 \cdot 1) - 1 \cdot (1 \cdot 1 - (-1) \cdot 1)
+(1)(11(1)(1))=40+ (-1) \cdot (1 \cdot 1 - (-1) \cdot (-1)) = -4 \neq 0

matrix AA is invertible and the system has a unique solution.

According to Cramer's rule:

x1=1detAdet(201140113011)=1204=30x_1 = \frac{1}{\det A} \cdot \det \begin{pmatrix} 20 & 1 & -1 \\ 40 & -1 & 1 \\ 30 & 1 & 1 \end{pmatrix} = \frac{-120}{-4} = 30
x2=1detAdet(120114011301)=1004=25x_2 = \frac{1}{\det A} \cdot \det \begin{pmatrix} 1 & 20 & -1 \\ 1 & 40 & 1 \\ -1 & 30 & 1 \end{pmatrix} = \frac{-100}{-4} = 25
x3=1detAdet(112011401130)=1404=35x_3 = \frac{1}{\det A} \cdot \det \begin{pmatrix} 1 & 1 & 20 \\ 1 & -1 & 40 \\ -1 & 1 & 30 \end{pmatrix} = \frac{-140}{-4} = 35

Verification shows that Axb=0A \cdot x - b = 0.

Solution Properties for Integer Matrices

If AZn×nA \in \mathbb{Z}^{n \times n} is an invertible matrix with integer elements and bZnb \in \mathbb{Z}^n is a vector with integer elements, then the elements of the inverse A1A^{-1} and solution xx of the system Ax=bA \cdot x = b are rational numbers with denominator that (if not reduced) equals detA|\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 detA\det A.