Editing Determinant (section)

=== Further methods ===
The order <math>\operatorname O(n^3)</math> reached by decomposition methods has been improved by different methods. If two matrices of order <math>n</math> can be multiplied in time <math>M(n)</math>, where <math>M(n) \ge n^a</math> for some <math>a>2</math>, then there is an algorithm computing the determinant in time <math>O(M(n))</math>.<ref>{{harvnb|Bunch|Hopcroft|1974}}</ref> This means, for example, that an <math>\operatorname O(n^{2.376})</math> algorithm for computing the determinant exists based on the [[Coppersmith–Winograd algorithm]]. This exponent has been further lowered, as of 2016, to 2.373.<ref>{{harvnb|Fisikopoulos|Peñaranda|2016|loc=§1.1}}</ref>

In addition to the complexity of the algorithm, further criteria can be used to compare algorithms.
Especially for applications concerning matrices over rings, algorithms that compute the determinant without any divisions exist. (By contrast, Gauss elimination requires divisions.) One such algorithm, having complexity <math>\operatorname O(n^4)</math> is based on the following idea: one replaces permutations (as in the Leibniz rule) by so-called [[closed ordered walk]]s, in which several items can be repeated. The resulting sum has more terms than in the Leibniz rule, but in the process several of these products can be reused, making it more efficient than naively computing with the Leibniz rule.<ref>{{harvnb|Rote|2001}}</ref> Algorithms can also be assessed according to their [[bit complexity]], i.e., how many bits of accuracy are needed to store intermediate values occurring in the computation. For example, the [[Gaussian elimination]] (or LU decomposition) method is of order <math>\operatorname O(n^3)</math>, but the bit length of intermediate values can become exponentially long.<ref>{{Cite conference
  | first1 = Xin Gui
  | last1 = Fang
  | first2 = George
  | last2 = Havas
  | title = On the worst-case complexity of integer Gaussian elimination
  | book-title = Proceedings of the 1997 international symposium on Symbolic and algebraic computation
  | conference = ISSAC '97
  | pages = 28–31
  | publisher = ACM
  | year = 1997
  | location = Kihei, Maui, Hawaii, United States
  | url = http://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/ft_gateway.cfm.pdf
  | doi = 10.1145/258726.258740
  | isbn = 0-89791-875-4
  | access-date = 2011-01-22
  | archive-url = https://web.archive.org/web/20110807042828/http://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/ft_gateway.cfm.pdf
  | archive-date = 2011-08-07
  | url-status = dead
  }}</ref> By comparison, the [[Bareiss Algorithm]], is an exact-division method (so it does use division, but only in cases where these divisions can be performed without remainder) is of the same order, but the bit complexity is roughly the bit size of the original entries in the matrix times <math>n</math>.<ref>{{harvnb|Fisikopoulos|Peñaranda|2016|loc=§1.1}}, {{harvnb|Bareiss|1968}}</ref>

If the determinant of ''A'' and the inverse of ''A'' have already been computed, the [[matrix determinant lemma]] allows rapid calculation of the determinant of {{math|''A'' + ''uv''<sup>T</sup>}}, where ''u'' and ''v'' are column vectors.

Charles Dodgson (i.e. [[Lewis Carroll]] of ''[[Alice's Adventures in Wonderland]]'' fame) invented a method for computing determinants called [[Dodgson condensation]].  Unfortunately this interesting method does not always work in its original form.<ref>{{Cite journal |last=Abeles |first=Francine F. |date=2008 |title=Dodgson condensation: The historical and mathematical development of an experimental method |url=https://www.academia.edu/10352246 |journal=Linear Algebra and Its Applications |language=en |volume=429 |issue=2–3 |pages=429–438 |doi=10.1016/j.laa.2007.11.022|doi-access=free }}</ref>