6
$\begingroup$

I am not sure if Cramer's rule is used for computation purposes. Your help would mean a lot. Thanks!

$\endgroup$
  • $\begingroup$ no. check some linear analisys book. like burden or Kincaid $\endgroup$ – Luis Felipe Oct 6 '15 at 11:56
  • 1
    $\begingroup$ It has rather theoretical importance. It is used to prove some theorems in linear algebra. $\endgroup$ – user137035 Oct 6 '15 at 12:00
  • $\begingroup$ See this as well. $\endgroup$ – J. M. is a poor mathematician Oct 6 '15 at 14:43
  • $\begingroup$ Cramer's rule is often handy for small, fixed-size matrices like 3x3. I use it in computer graphics work occasionally. $\endgroup$ – Tavian Barnes Oct 6 '15 at 17:41
  • 1
    $\begingroup$ Actually I would go a step further than "don't use Cramer's rule". If you are calculating the determinant or the inverse of a matrix as part of a bigger algorithm, that is almost always a bad thing to do. Mathematical formulas using matrix inverses often look neat, but that doesn't mean they are the best way to calculate something. $\endgroup$ – alephzero Oct 6 '15 at 18:16
12
$\begingroup$

Cramer is highly inefficient, of time complexity $O(n! \times n)$ with a naive determinant-finding algorithm, and $O(n^4)$ with e.g. LU decomposition. Gaussian elimination has cubic complexity.

$\endgroup$
  • 2
    $\begingroup$ That's only if the deteminant is computer by definition. It may be computed by LU decomposition as well, in which case the complexity would be $O(n^4)$. $\endgroup$ – Sasha Oct 6 '15 at 11:56
  • $\begingroup$ Fair enough. I'll add that in, thanks. $\endgroup$ – Patrick Stevens Oct 6 '15 at 11:57
  • $\begingroup$ On a tangent: is there a difference between $O(n! \times n)$ and $O(n!)$? I'm thinking $O(n! \times n) \approx O((n+1)!) \approx O(n!)$? $\endgroup$ – Nick T Oct 6 '15 at 21:06
  • 1
    $\begingroup$ $O((n+1)!)$ is not $O(n!)$ any more than $O(n^{k+1})$ is $O(n^k)$. $\endgroup$ – R.. Oct 6 '15 at 21:22
3
$\begingroup$

Reducing the matrix to triangular form and multiplying the elements on the diagonal is usually quicker. I am pretty sure that is the algorithm most computer algebra systems use, unless it is known in advance that the matrix has some special properties. Sometimes Laplace expansion can be quicker if the matrix has many zeros along some rows/columns.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.