Cramer's rule

The Cramer's rule or determinants method is a mathematical formula for solving a system of linear equations . It is helpful for the theoretical consideration of linear systems of equations. However, the computational effort is usually too high to calculate a solution, since a relatively large number of determinants occur. Therefore, other methods from numerical mathematics are used. Cramer's rule is named after Gabriel Cramer , who published it in 1750, but Leibniz had already found it.

rule

Given is a linear system of equations with as many equations as there are unknowns in the form

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}\,+&\cdots &+\,a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+a_{22}x_{2}\,+&\cdots &+\,a_{2n}x_{n}&=&b_{2}\\&&&\vdots &\\a_{n1}x_{1}+a_{n2}x_{2}\,+&\cdots &+\,a_{nn}x_{n}&=&b_{n}\end{matrix}}}$

or in matrix notation with ${\displaystyle Ax=b}$

${\displaystyle A={\begin{pmatrix}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{pmatrix}}\,,\quad x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}}\,,\quad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{n}\end{pmatrix}}\,.}$

It is also assumed that the square coefficient matrix is ​​regular (invertible). This is the case if and only if is. ${\displaystyle A}$ ${\displaystyle \det(A)\neq 0}$

Then the system of equations is uniquely solvable and the components of the uniquely determined solution vector are given by ${\displaystyle x_{i}}$ ${\displaystyle x}$

${\displaystyle x_{i}={\frac {\det(A_{i})}{\det(A)}}}$for everyone . ${\displaystyle i}$

Here is the matrix that is formed by replacing the -th column of the coefficient matrix with the right-hand side of the system of equations : ${\displaystyle A_{i}}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle b}$

${\displaystyle A_{i}={\begin{pmatrix}a_{1,1}&\cdots &a_{1,i-1}&b_{1}&a_{1,i+1}&\cdots &a_{1,n}\\a_{2,1}&\cdots &a_{2,i-1}&b_{2}&a_{2,i+1}&\cdots &a_{2,n}\\\vdots &&\vdots &\vdots &\vdots &&\vdots \\a_{n,1}&\cdots &a_{n,i-1}&b_{n}&a_{n,i+1}&\cdots &a_{n,n}\end{pmatrix}}}$

Examples

2nd order linear system of equations

This example is based on the following system of linear equations:

${\displaystyle {\begin{matrix}\color {blue}{1}\,\color {black}x_{1}+\color {blue}{2}\,\color {black}x_{2}=\color {green}{3}\\\color {blue}{4}\,\color {black}x_{1}+\color {blue}{5}\,\color {black}x_{2}=\color {green}{6}\end{matrix}}}$

The extended coefficient matrix of the system of equations is then:

${\displaystyle {\begin{pmatrix}\color {blue}{A}&\color {green}b\end{pmatrix}}=\left({\begin{array}{cc|c}\color {blue}{1}&\color {blue}{2}&\color {green}{3}\\\color {blue}{4}&\color {blue}{5}&\color {green}{6}\end{array}}\right)}$

According to Cramer's rule, its solution is calculated as follows:

${\displaystyle x_{1}={\frac {\det(A_{1})}{\det(A)}}={\frac {\det {\begin{pmatrix}\color {green}{3}&\color {blue}{2}\\\color {green}{6}&\color {blue}{5}\end{pmatrix}}}{\det {\begin{pmatrix}\color {blue}{1}&\color {blue}{2}\\\color {blue}{4}&\color {blue}{5}\end{pmatrix}}}}={\frac {3}{-3}}=-1\qquad }$

${\displaystyle x_{2}={\frac {\det(A_{2})}{\det(A)}}={\frac {\det {\begin{pmatrix}\color {blue}{1}&\color {green}{3}\\\color {blue}{4}&\color {green}{6}\end{pmatrix}}}{\det {\begin{pmatrix}\color {blue}{1}&\color {blue}{2}\\\color {blue}{4}&\color {blue}{5}\end{pmatrix}}}}={\frac {-6}{-3}}=2}$

3rd order linear system of equations

This example is based on the following system of linear equations:

${\displaystyle {\begin{matrix}\color {blue}{82}\,\color {black}x_{1}+\color {blue}{45}\,\color {black}x_{2}+\color {blue}{9}\,\color {black}x_{3}=\color {green}{1}\\\color {blue}{27}\,\color {black}x_{1}+\color {blue}{16}\,\color {black}x_{2}+\color {blue}{3}\,\color {black}x_{3}=\color {green}{1}\\\color {blue}{9}\,\color {black}x_{1}+\color {blue}{5}\,\color {black}x_{2}+\color {blue}{1}\,\color {black}x_{3}=\color {green}{0}\\\end{matrix}}}$

The extended coefficient matrix of the system of equations is then:

${\displaystyle {\begin{pmatrix}\color {blue}{A}&\color {green}b\end{pmatrix}}=\left({\begin{array}{ccc|c}\color {blue}{82}&\color {blue}{45}&\color {blue}{9}&\color {green}{1}\\\color {blue}{27}&\color {blue}{16}&\color {blue}{3}&\color {green}{1}\\\color {blue}{9}&\color {blue}{5}&\color {blue}{1}&\color {green}{0}\end{array}}\right)}$

According to Cramer's rule, the solution of the system of equations is calculated as follows:

${\displaystyle x_{1}={\frac {\det(A_{1})}{\det(A)}}={\frac {\det {\begin{pmatrix}\color {green}{1}&\color {blue}{45}&\color {blue}{9}\\\color {green}{1}&\color {blue}{16}&\color {blue}{3}\\\color {green}{0}&\color {blue}{5}&\color {blue}{1}\end{pmatrix}}}{\det {\begin{pmatrix}\color {blue}{82}&\color {blue}{45}&\color {blue}{9}\\\color {blue}{27}&\color {blue}{16}&\color {blue}{3}\\\color {blue}{9}&\color {blue}{5}&\color {blue}{1}\end{pmatrix}}}}={\frac {1}{1}}=1\qquad }$

${\displaystyle x_{2}={\frac {\det(A_{2})}{\det(A)}}={\frac {\det {\begin{pmatrix}\color {blue}{82}&\color {green}{1}&\color {blue}{9}\\\color {blue}{27}&\color {green}{1}&\color {blue}{3}\\\color {blue}{9}&\color {green}{0}&\color {blue}{1}\end{pmatrix}}}{\det {\begin{pmatrix}\color {blue}{82}&\color {blue}{45}&\color {blue}{9}\\\color {blue}{27}&\color {blue}{16}&\color {blue}{3}\\\color {blue}{9}&\color {blue}{5}&\color {blue}{1}\end{pmatrix}}}}={\frac {1}{1}}=1\qquad }$

${\displaystyle x_{3}={\frac {\det(A_{3})}{\det(A)}}={\frac {\det {\begin{pmatrix}\color {blue}{82}&\color {blue}{45}&\color {green}{1}\\\color {blue}{27}&\color {blue}{16}&\color {green}{1}\\\color {blue}{9}&\color {blue}{5}&\color {green}{0}\end{pmatrix}}}{\det {\begin{pmatrix}\color {blue}{82}&\color {blue}{45}&\color {blue}{9}\\\color {blue}{27}&\color {blue}{16}&\color {blue}{3}\\\color {blue}{9}&\color {blue}{5}&\color {blue}{1}\end{pmatrix}}}}={\frac {-14}{1}}=-14}$

history

The Cramer rule was published in 1750 by Gabriel Cramer in Appendix 1 of his book "Introduction à l'analyse des lignes courbes algébriques". He explicitly stated the formulas for linear systems of equations with up to three equations and described how the solution formulas for systems of equations with more equations can be created. Since the determinant had not yet been introduced, he used fractions with a polynomial each in the numerator and denominator. As the following excerpt from the original work shows, these are identical to the polynomials of the Leibniz formula .

This example also shows that Cramer did not yet use today's notation of linear systems of equations. With this, the formula is as follows:

${\displaystyle x_{1}={\frac {b_{1}a_{22}a_{33}-b_{1}a_{32}a_{23}-b_{2}a_{12}a_{33}+b_{2}a_{32}a_{13}+b_{3}a_{12}a_{23}-b_{3}a_{22}a_{13}}{a_{11}a_{22}a_{33}-a_{11}a_{32}a_{23}-a_{21}a_{12}a_{33}+a_{21}a_{32}a_{13}+a_{31}a_{12}a_{23}-a_{31}a_{22}a_{13}}}}$

Cramer himself was aware that linear systems of equations cannot always be solved unambiguously. Étienne Bézout then showed in 1764 that the denominator becomes zero when the system of equations cannot be solved uniquely. Furthermore, Cramer gave no proof of his formula. This was only supplied by Augustin Louis Cauchy in 1815. He also introduced the notation of Cramer's rule used today.

Gottfried Wilhelm Leibniz put Cramer's rule on paper as early as 1678 in a manuscript. However, this was only discovered later and therefore had no effect on the development of solution methods for linear systems of equations. Colin Maclaurin described in his work "Treatise of Algebra", which was published in 1748, the special cases of Cramer's rule for linear systems of two or three equations. Although he had the idea of ​​expanding these formulas to systems of equations with several equations, in contrast to Cramer, he found no rule on how to correctly set the signs in the polynomials used. In the 20th century, Carl Benjamin Boyer sparked a dispute among mathematics historians as to whether Maclaurin or Cramer was the discoverer of the formula. He also recommended renaming it to the Maclaurin-Cramer rule.

Computing effort

In order to solve a linear system of equations with unknowns using Cramer's rule , determinants have to be calculated. The number of arithmetic operations to be carried out depends solely on the algorithm for calculating the determinants. ${\displaystyle n}$ ${\displaystyle n+1}$

If the determinants are calculated using the Leibniz formula as by Cramer, then multiplications and additions are necessary for each determinant . Even with a system of four equations, 360 multiplications, 115 additions and 4 divisions are necessary. Compared to other procedures, this is a very large number of operations. Even with the use of efficient algorithms for calculating determinants, the computational effort for solving a linear system of equations with Cramer's rule is significantly higher than, for example, with the Gaussian elimination method . ${\displaystyle (n-1)\cdot n!}$ ${\displaystyle n!-1}$

When calculating a matrix on a computer with floating point operations per second (100 Mflops) the following calculation times would result: ${\displaystyle n\times n}$ ${\displaystyle 10^{8}}$

n	10	12	14th	16	18th	20th
Computing time	0.4 s	1 min	3.6 h	41 days	38 years	16,000 years

proof

For this proof, a matrix is ​​used that is created by replacing the -th column of the identity matrix with the solution vector of the system of equations . For a system of equations with four equations it looks like this : ${\displaystyle X_{i}}$ ${\displaystyle i}$ ${\displaystyle x}$ ${\displaystyle Ax=b}$ ${\displaystyle X_{2}}$

${\displaystyle X_{2}={\begin{pmatrix}1&x_{1}&0&0\\0&x_{2}&0&0\\0&x_{3}&1&0\\0&x_{4}&0&1\end{pmatrix}}}$

This example also shows that it is true. ${\displaystyle AX_{i}=A_{i}}$

${\displaystyle {\begin{aligned}A\cdot X_{2}&={\begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\\a_{21}&a_{22}&a_{23}&a_{24}\\a_{31}&a_{32}&a_{33}&a_{34}\\a_{41}&a_{42}&a_{43}&a_{44}\end{pmatrix}}\cdot {\begin{pmatrix}1&x_{1}&0&0\\0&x_{2}&0&0\\0&x_{3}&1&0\\0&x_{4}&0&1\end{pmatrix}}\\&={\begin{pmatrix}a_{11}&a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}+a_{14}x_{4}&a_{13}&a_{14}\\a_{21}&a_{21}x_{1}+a_{22}x_{2}+a_{23}x_{3}+a_{24}x_{4}&a_{23}&a_{24}\\a_{31}&a_{31}x_{1}+a_{32}x_{2}+a_{33}x_{3}+a_{34}x_{4}&a_{33}&a_{34}\\a_{41}&a_{41}x_{1}+a_{42}x_{2}+a_{43}x_{3}+a_{44}x_{4}&a_{43}&a_{44}\end{pmatrix}}\\&={\begin{pmatrix}a_{11}&b_{1}&a_{13}&a_{14}\\a_{21}&b_{2}&a_{23}&a_{24}\\a_{31}&b_{3}&a_{33}&a_{34}\\a_{41}&b_{4}&a_{43}&a_{44}\end{pmatrix}}\\&=A_{2}\end{aligned}}}$

Since, in addition , it follows with the product rule for determinants ${\displaystyle \det(X_{i})=x_{i}}$

${\displaystyle {\begin{matrix}\det(A)&\cdot &\det(X_{i})&=&\det(A_{i})\\\det(A)&\cdot &x_{i}&=&\det(A_{i})\\&&x_{i}&=&\det(A_{i})\cdot \det(A)^{-1}\end{matrix}}}$

Since the determinant is not the zero element according to the assumption, exists . ${\displaystyle \det(A)}$ ${\displaystyle \det(A)^{-1}}$

generalization

A generalization - and at the same time a step in the proof - of Cramer's rule is represented by the following theorem: Given is a quadratic system of linear equations of form

${\displaystyle Ax=b}$.

If there is a solution to this system of linear equations, then applies ${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$

${\displaystyle \det(A)\cdot x_{i}=\det(A_{i})}$for each . ${\displaystyle i}$

The matrix is created from the coefficient matrix by replacing the -th column of with the right-hand side of the system of equations . ${\displaystyle A_{i}}$ ${\displaystyle A}$ ${\displaystyle i}$ ${\displaystyle A}$ ${\displaystyle b}$

There is no restriction to a clearly solvable system of equations. In addition, since division no longer occurs, the theorem applies to all systems of equations with coefficients from a commutative ring . This generalization is no longer called Cramer's rule.

Inferences from Cramer's rule

The inverse of a matrix

The individual columns of the inverse of a matrix are each formed by the solution of the system of equations with the -th unit vector on the right-hand side. If this is calculated with Cramer's rule, the formula is obtained using the adjuncts ${\displaystyle A}$ ${\displaystyle Ax=e_{j}}$ ${\displaystyle j}$ ${\displaystyle \operatorname {adj} (A)}$

${\displaystyle A^{-1}={\frac {1}{\det(A)}}\operatorname {adj} (A)}$

This formula also shows a property of matrices with entries from a commutative ring instead of a field . These are therefore invertible if and only if is invertible. ${\displaystyle \det(A)}$

Solution of a homogeneous system of linear equations

With the help of Cramer's rule it can easily be shown that the trivial solution is the only solution of every homogeneous system of linear equations . Since there are only zeros in the -th column of all matrices , their columns are no longer linearly independent , and it therefore applies . So they all calculate to zero. ${\displaystyle x_{1}=x_{2}=\dotsb =x_{n}=0}$ ${\displaystyle \det(A)\neq 0}$ ${\displaystyle A_{i}}$ ${\displaystyle i}$ ${\displaystyle \det(A_{i})=0}$ ${\displaystyle x_{i}}$

From the above property follows directly that the core of a linear system with the zero vector and this therefore has a unique solution. ${\displaystyle Ax=b}$ ${\displaystyle \det(A)\neq 0}$

Individual evidence

1. ↑ It is assumed that the coefficients are real or complex numbers or - more generally - elements of a field .
2. ^ Gabriel Cramer : Introduction à l'analyse des lignes courbes algébriques. Geneva 1750, pp. 657-659.
3. ↑ ^{a b c} Jean-Luc Chabert et al .: A History of Algorithms. From the pebble to the microchip. Springer-Verlag, 1999, ISBN 3-540-63369-3 , pp. 284-287 (This book contains an English translation of Cramer's original publication.).
4. ^ Antoni A. Kosinski: Cramer's Rule Is Due to Cramer. In: Mathematics Magazine. Vol. 74, No. 4, October 2001, pp. 310-312.
5. ↑ Bruce A. Hedman: An Earlier Date for "Cramer's Rule" In: Historica Mathematica. Vol. 24, 1999, pp. 365-368.
6. ↑ W. Dahmen, A. Reusken: Numerics for engineers and natural scientists, Springer, 2006, ISBN 3-540-25544-3
7. ^ Serge Lang : Algebra. 2nd Edition. Addison-Wesley, 1984, ISBN 0-201-05487-6 , p. 451.