37 lines
2.1 KiB
Text
37 lines
2.1 KiB
Text
;Related tasks:
|
|
* [[Arrays]]
|
|
* [[Vector]]
|
|
* [[Matrices]]
|
|
** [[Determinant and permanent]]
|
|
*** [[wp:Laplace_expansion|Laplace expansion]] <math>O\bigl(n!\bigr)</math>
|
|
*** [[wp:Leibniz_formula_for_determinants|Leibniz fomula]] <math>\Omega\bigl(n!\cdot n\bigr)</math>
|
|
*** [[wp:Bareiss_algorithm|Bareiss algorithm]] <math>O\bigl(n^3\bigr)</math>
|
|
*** [[wp:LU_decomposition|LU-decomposition]] <math>O\bigl(n^3\bigr)</math>
|
|
*** [[wp:Strassen_algorithm|Strassen algorithm]] <math>O\bigl(n^{2.807}\bigr)</math>
|
|
*** [[wp:Coppersmith%E2%80%93Winograd_algorithm|Coppersmith-Winograd algorithm]] <math>O\bigl(n^{2.376}\bigr)</math>
|
|
*** [[wp:Jean-Fran%C3%A7ois_Le_Gall|Le Gall algorithm]]
|
|
*** [https://codegolf.stackexchange.com/questions/236835/birds-algorithm-for-computing-determinants Bird's algorithm]
|
|
* [[Bivector]]
|
|
* [[Antivector]]
|
|
* [[Tensor]]
|
|
* [[Quaternion]]
|
|
* [[Rotor]]
|
|
* [[Motor]]
|
|
* [[Sedenion]]
|
|
* [[Octonion]]
|
|
<br>
|
|
For a given matrix, return the [[wp:Determinant|determinant]] and the [[wp:Permanent_(mathematics)|permanent]] of the matrix.
|
|
For a matrix of [[wp:Orthonormal_basis|orthonormal basis]] vectors, return the [[wp:Levi-Civita_symbol|Levi-Civita symbol]] of the orthonormal basis vector permutation.
|
|
|
|
The determinant is given by
|
|
:: <big><math>\det(A) = \sum_\sigma\sgn(\sigma)\prod_{i=1}^n M_{i,\sigma_i}</math></big>
|
|
while the permanent is given by
|
|
:: <big><math> \operatorname{perm}(A)=\sum_\sigma\prod_{i=1}^n M_{i,\sigma_i}</math></big>
|
|
In both cases the sum is over the permutations <math>\sigma</math> of the permutations of 1, 2, ..., ''n''. (A permutation's sign is 1 if there are an even number of inversions and -1 otherwise; see [[wp:Parity of a permutation|parity of a permutation]].)
|
|
<br><br>
|
|
;C.f.
|
|
* [[wp:Computational_complexity_of_matrix_multiplication#Matrix_inversion,_determinant_and_Gaussian_elimination|Computational complexity of matrix multiplication]]
|
|
* [https://dai.fmph.uniba.sk/courses/FPRO/bird_pearls.pdf Richard Bird Pearls]
|
|
* [https://dai.fmph.uniba.sk/courses/FPRO/ Funkcionálne programovanie]
|
|
* [[Permutations by swapping]]
|
|
|