# Nakafa Framework: LLM

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

Output docs content for large language models.

---

export const metadata = {
    title: "Cramer's Rule",
    description: "Solve linear systems using determinants with Cramer's rule. Learn complementary matrices, inverse formulas, and step-by-step examples for AI applications.",
    authors: [{ name: "Nabil Akbarazzima Fatih" }],
    date: "07/12/2025",
    subject: "Linear Methods of AI",
};

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

<MathContainer>
<BlockMath math="\tilde{A} = (\tilde{a}_{ij})_{i=1,\ldots,n \atop j=1,\ldots,n} \in \mathbb{R}^{n \times n}" />
</MathContainer>

with elements:

<BlockMath math="\tilde{a}_{ij} = (-1)^{i+j} \cdot \det A_{ji}" />

Note that the indices in <InlineMath math="A_{ji}" /> are swapped (not <InlineMath math="A_{ij}" />).

The complementary matrix <InlineMath math="\tilde{A}" /> is a matrix consisting of **cofactors** of matrix <InlineMath math="A" />, but with transposed positions.

### Structure of Complementary Matrix

The complementary matrix has the following structure:

<MathContainer>
<BlockMath 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}" />
</MathContainer>

Each element is calculated by taking the determinant of the corresponding submatrix, then given a sign based on the checkerboard pattern <InlineMath math="(-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:

<MathContainer>
<BlockMath 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}" />
</MathContainer>

In other words:

<BlockMath 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 <InlineMath math="A \in \mathbb{R}^{n \times n}" /> is invertible, then:

<MathContainer>
<BlockMath math="A^{-1} = \frac{1}{\det A} \cdot \tilde{A}" />
</MathContainer>

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 <InlineMath math="n = 2" />:

<BlockMath math="A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}" />

Its determinant is:

<BlockMath math="\det A = a \cdot d - b \cdot c" />

Its complementary matrix is:

<BlockMath math="\tilde{A} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}" />

So its inverse is:

<MathContainer>
<BlockMath math="A^{-1} = \frac{1}{a \cdot d - b \cdot c} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}" />
</MathContainer>

We can verify that:

<MathContainer>
<BlockMath 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}" />
<BlockMath math="= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I" />
</MathContainer>

## Theorem Statement

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

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

<MathContainer>
<BlockMath math="x_j = \frac{\det(a^1 \; \ldots \; a^{j-1} \; b \; a^{j+1} \; \ldots \; a^n)}{\det A}" />
</MathContainer>

for <InlineMath math="j = 1, 2, \ldots, n" />.

To calculate the <InlineMath math="j" />-th component of solution <InlineMath math="x" />, we replace the <InlineMath math="j" />-th column of matrix <InlineMath math="A" /> with vector <InlineMath math="b" />, then calculate the determinant of this modified matrix and divide it by the determinant of the original matrix <InlineMath math="A" />.

## Proof Using Laplace Expansion

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

For <InlineMath math="j = 1, \ldots, n" />:

<MathContainer>
<BlockMath 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" />
</MathContainer>

<MathContainer>
<BlockMath math="= \frac{1}{\det A} \sum_{i=1}^{n} (-1)^{i+j} \cdot \det A_{ij} \cdot b_i" />
<BlockMath math="= \frac{1}{\det A} \cdot \det(a^1 \; \ldots \; a^{j-1} \; b \; a^{j+1} \; \ldots \; a^n)" />
</MathContainer>

based on Laplace expansion with respect to the <InlineMath math="j" />-th column.

## Application Example

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

<MathContainer>
<BlockMath math="A = \begin{pmatrix} 1 & 1 & -1 \\ 1 & -1 & 1 \\ -1 & 1 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} 20 \\ 40 \\ 30 \end{pmatrix}" />
</MathContainer>

Since:

<MathContainer>
<BlockMath math="\det A = 1 \cdot ((-1) \cdot 1 - 1 \cdot 1) - 1 \cdot (1 \cdot 1 - (-1) \cdot 1)" />
<BlockMath math="+ (-1) \cdot (1 \cdot 1 - (-1) \cdot (-1)) = -4 \neq 0" />
</MathContainer>

matrix <InlineMath math="A" /> is invertible and the system has a unique solution.

According to Cramer's rule:

<MathContainer>
<BlockMath 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" />
</MathContainer>

<MathContainer>
<BlockMath 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" />
</MathContainer>

<MathContainer>
<BlockMath 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" />
</MathContainer>

Verification shows that <InlineMath math="A \cdot x - b = 0" />.

## Solution Properties for Integer Matrices

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