Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cramer's rule
Summary
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 (1704–1752), who published the rule for an arbitrary number of unknowns in 1750, although Colin Maclaurin also published special cases of the rule in 1748 (and possibly knew of it as early as 1729).
Cramer's rule implemented in a naive way is computationally inefficient for systems of more than two or three equations. 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. Cramer's rule can also be numerically unstable even for 2×2 systems. However, it has recently been shown that Cramer's rule can be implemented with the same complexity as Gaussian elimination, (consistently requires twice as many arithmetic operations and has the same numerical stability when the same permutation matrices are applied).
Consider a system of n linear equations for n unknowns, represented in matrix multiplication form as follows:
where the n × n matrix A has a nonzero determinant, and the vector 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:
where 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 considers the matrix equation
where the n × n matrix A has a nonzero determinant, and X, B are n × m matrices. Given sequences and , let be the k × k submatrix of X with rows in and columns in . Let be the n × n matrix formed by replacing the column of A by the column of B, for all .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.