Cramer’s Rule

by admin in Matlab on May 15, 2019

In linear algebra, Cramer’s rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of the (square) coefficient matrix and of matrices obtained from it by replacing one column by the column vector of right-hand-sides of the equations. It is named after Gabriel Cramer (1704–1752), who published the rule for an arbitrary number of unknowns in 1750,[1][2] although Colin Maclaurin also published special cases of the rule in 1748[3] (and possibly knew of it as early as 1729).[4][5][6]

Cramer’s rule implemented in a naïve way is computationally inefficient for systems of more than two or three equations.[7] In the case of n equations in n unknowns, it requires computation of n + 1 determinants, while Gaussian elimination produces the result with the same computational complexity as the computation of a single determinant.[8][9] Cramer’s rule can also be numerically unstable even for 2×2 systems.[10] However, it has recently been shown that Cramer’s rule can be implemented in O(n3) time,[11] which is comparable to more common methods of solving systems of linear equations, such as Gaussian elimination (consistently requiring 2.5 times as many arithmetic operations for all matrix sizes), while exhibiting comparable numeric stability in most cases.In linear algebra cramer’s rule is an explicit formula for the solution of a system of linear equation

Contents

  • General case
  • Finding inverse matrix
  • Applications
    • Explicit formulas for small systems
  • References

General Case

Consider a system of n linear equations for n unknowns, represented in matrix multiplication form as follows:

Ax=b

where the n × n matrix A has a nonzero determinant, and the vector {x = (x1 …,xn)^{T} is the column vector of the variables. Then the theorem states that in this case the system has a unique solution, whose individual values for the unknowns are given by:

x_{i}={\frac {\det(A_{i})}{\det(A)}}\qquad i=1,\ldots ,n

where {Ai} is the matrix formed by replacing the i-th column of A by the column vector b.

A more general version of Cramer’s rule[12] considers the matrix equation

AX=B

Finding Inverse Matrix

Let A be an n × n matrix. Then

{\displaystyle A\,\operatorname {adj} A=(\operatorname {adj} A)\,A=\operatorname {det} (A)I}

where adj(A) denotes the adjugate matrix of A, det(A) is the determinant, and I is the identity matrix. If det(A) is invertible in R, then the inverse matrix of A is

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

If R is a field (such as the field of real numbers), then this gives a formula for the inverse of A, provided det(A) ≠ 0. In fact, this formula will work whenever R is a commutative ring, provided that det(A) is a unit. If det(A) is not a unit, then A is not invertible.

Matlab Code

Applications

Explicit formulas for small systems

Consider the linear system

\left\{{\begin{matrix}a_{1}x+b_{1}y&={\color {red}c_{1}}\\a_{2}x+b_{2}y&={\color {red}c_{2}}\end{matrix}}\right.

which in matrix format is

{\begin{bmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}{\color {red}c_{1}}\\{\color {red}c_{2}}\end{bmatrix}}.

Assume a1b2 − b1a2 nonzero. Then, with help of determinants, x and y can be found with Cramer’s rule as

{\displaystyle {\begin{aligned}x&={\frac {\begin{vmatrix}{\color {red}{c_{1}}}&b_{1}\\{\color {red}{c_{2}}}&b_{2}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{vmatrix}}}={{\color {red}c_{1}}b_{2}-b_{1}{\color {red}c_{2}} \over a_{1}b_{2}-b_{1}a_{2}},\quad y={\frac {\begin{vmatrix}a_{1}&{\color {red}{c_{1}}}\\a_{2}&{\color {red}{c_{2}}}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}\\a_{2}&b_{2}\end{vmatrix}}}={a_{1}{\color {red}c_{2}}-{\color {red}c_{1}}a_{2} \over a_{1}b_{2}-b_{1}a_{2}}\end{aligned}}.}

The rules for 3 × 3 matrices are similar. Given

\left\{{\begin{matrix}a_{1}x+b_{1}y+c_{1}z&={\color {red}d_{1}}\\a_{2}x+b_{2}y+c_{2}z&={\color {red}d_{2}}\\a_{3}x+b_{3}y+c_{3}z&={\color {red}d_{3}}\end{matrix}}\right.

which in matrix format is

{\begin{bmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}{\color {red}d_{1}}\\{\color {red}d_{2}}\\{\color {red}d_{3}}\end{bmatrix}}.

Then the values of x, y and z can be found as follows:

x={\frac {\begin{vmatrix}{\color {red}d_{1}}&b_{1}&c_{1}\\{\color {red}d_{2}}&b_{2}&c_{2}\\{\color {red}d_{3}}&b_{3}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},\quad y={\frac {\begin{vmatrix}a_{1}&{\color {red}d_{1}}&c_{1}\\a_{2}&{\color {red}d_{2}}&c_{2}\\a_{3}&{\color {red}d_{3}}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},{\text{ and }}z={\frac {\begin{vmatrix}a_{1}&b_{1}&{\color {red}d_{1}}\\a_{2}&b_{2}&{\color {red}d_{2}}\\a_{3}&b_{3}&{\color {red}d_{3}}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}}.

References

  1. ^ Cramer, Gabriel (1750). “Introduction à l’Analyse des lignes Courbes algébriques” (in French). Geneva: Europeana. pp. 656–659. Retrieved 2012-05-18.
  2. ^ Kosinski, A. A. (2001). “Cramer’s Rule is due to Cramer”. Mathematics Magazine74: 310–312. doi:10.2307/2691101.
  3. ^ MacLaurin, Colin (1748). A Treatise of Algebra, in Three Parts.
  4. ^ Boyer, Carl B. (1968). A History of Mathematics (2nd ed.). Wiley. p. 431.
  5. ^ Katz, Victor (2004). A History of Mathematics (Brief ed.). Pearson Education. pp. 378–379.
  6. ^ Hedman, Bruce A. (1999). “An Earlier Date for “Cramer’s Rule”” (PDF). Historia Mathematica26 (4): 365–368. doi:10.1006/hmat.1999.2247.
  7. ^ David Poole (2014). Linear Algebra: A Modern Introduction. Cengage Learning. p. 276. ISBN 978-1-285-98283-0.
  8. ^ Joe D. Hoffman; Steven Frankel (2001). Numerical Methods for Engineers and Scientists, Second Edition,. CRC Press. p. 30. ISBN 978-0-8247-0443-8.

Share Your Valuable Opinions