# Nakafa Learning Content

> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.

URL: https://nakafa.com/en/subjects/ai-ds/linear-methods/cramer-rule
Source: https://raw.githubusercontent.com/nakafaai/nakafa.com/refs/heads/main/packages/contents/material/lesson/ai-ds/linear-methods/cramer-rule/en.mdx

Solve linear systems using determinants with Cramer's rule. Learn complementary matrices, inverse formulas, and worked examples for AI applications.

---

## 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 $$A \in \mathbb{R}^{n \times n}$$, the complementary matrix is defined as:

Visible text: For matrix , the complementary matrix is defined as:

Component: MathContainer
Children:

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

with elements:

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

Note that the indices in $$A_{ji}$$ are swapped (not $$A_{ij}$$).

Visible text: Note that the indices in are swapped (not ).

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

Visible text: The complementary matrix is a matrix consisting of **cofactors** of matrix , but with transposed positions.

### Structure of Complementary Matrix

The complementary matrix has the following structure:

Component: MathContainer
Children:

```math
\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}$$.

Visible text: Each element is calculated by taking the determinant of the corresponding submatrix, then given a sign based on the checkerboard pattern .

## Fundamental Properties of Complementary Matrix

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

Component: MathContainer
Children:

```math
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:

```math
A \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 $$A \in \mathbb{R}^{n \times n}$$ is invertible, then:

Visible text: If matrix is invertible, then:

Component: MathContainer
Children:

```math
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 a Two-by-Two Matrix

For matrix $$n = 2$$:

Visible text: For matrix :

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

Its determinant is:

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

Its complementary matrix is:

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

So its inverse is:

Component: MathContainer
Children:

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

We can verify that:

Component: MathContainer
Children:

```math
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}
```

```math
= \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 $$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:

Visible text: Let be an invertible matrix and be the columns of . For vector , the solution of the linear equation system is given by:

Component: MathContainer
Children:

```math
x_j = \frac{\det(a^1 \; \ldots \; a^{j-1} \; b \; a^{j+1} \; \ldots \; a^n)}{\det A}
```

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

Visible text: for .

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$$.

Visible text: To calculate the -th component of solution , we replace the -th column of matrix with vector , then calculate the determinant of this modified matrix and divide it by the determinant of the original matrix .

## Proof Using Laplace Expansion

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

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

Visible text: For :

Component: MathContainer
Children:

```math
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
```

Component: MathContainer
Children:

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

```math
= \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 $$j$$-th column.

Visible text: based on Laplace expansion with respect to the -th column.

## Application Example

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

Component: MathContainer
Children:

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

Since:

Component: MathContainer
Children:

```math
\det A = 1 \cdot ((-1) \cdot 1 - 1 \cdot 1) - 1 \cdot (1 \cdot 1 - (-1) \cdot 1)
```

```math
+ (-1) \cdot (1 \cdot 1 - (-1) \cdot (-1)) = -4 \neq 0
```

matrix $$A$$ is invertible and the system has a unique solution.

Visible text: matrix is invertible and the system has a unique solution.

According to Cramer's rule:

Component: MathContainer
Children:

```math
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
```

Component: MathContainer
Children:

```math
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
```

Component: MathContainer
Children:

```math
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
```

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

Visible text: Verification shows that .

## Solution Properties for Integer Matrices

If $$A \in \mathbb{Z}^{n \times n}$$ is an invertible matrix with integer elements and $$b \in \mathbb{Z}^n$$ is a vector with integer elements, then the elements of the inverse $$A^{-1}$$ and solution $$x$$ of the system $$A \cdot x = b$$ are rational numbers with denominator that (if not reduced) equals $$|\det A|$$.

Visible text: If is an invertible matrix with integer elements and is a vector with integer elements, then the elements of the inverse and solution of the system are rational numbers with denominator that (if not reduced) equals .

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$$.

Visible text: 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 .