Cramer's rule

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-sides of the equations. It is named after Gabriel Cramer, 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 naive 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][verification needed] Cramer's rule can also be numerically unstable even for 2×2 systems.[10] However, Cramer's rule can be implemented with the same complexity as Gaussian elimination,[11][12] (consistently requires twice as many arithmetic operations and has the same numerical stability when the same permutation matrices are applied).

  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 Magazine. 74 (4): 310–312. doi:10.2307/2691101. JSTOR 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 Mathematica. 26 (4): 365–368. doi:10.1006/hmat.1999.2247. S2CID 121056843.
  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.
  9. ^ Thomas S. Shores (2007). Applied Linear Algebra and Matrix Analysis. Springer Science & Business Media. p. 132. ISBN 978-0-387-48947-6.
  10. ^ Nicholas J. Higham (2002). Accuracy and Stability of Numerical Algorithms: Second Edition. SIAM. p. 13. ISBN 978-0-89871-521-7.
  11. ^ Ken Habgood; Itamar Arel (2012). "A condensation-based application of Cramerʼs rule for solving large-scale linear systems". Journal of Discrete Algorithms. 10: 98–109. doi:10.1016/j.jda.2011.06.007.
  12. ^ G.I.Malaschonok (1983). "Solution of a System of Linear Equations in an Integral Ring". USSR J. Of Comput. Math. And Math. Phys. 23: 1497–1500. arXiv:1711.09452.