Return the determinant.
\[
\det A \qquad \mathbb{K}^{N\times N}\to\mathbb{K}
\]
Uses the Leibniz formula.
TODO: Filter zero products.
Complexity
There will be
- \(N!-1\) scalar additions (
+),
- \((N-1)N!\) scalar multiplications (
*),
so \(NN!-1\) arithmetic operations in total.
References
Wikipedia - Leibniz formula for determinants
Source code in linalg\leibniz.py
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96 | def det_leibniz(A:np.ndarray, progress:set[str]|Progress=set()) -> Any:
r"""Return the determinant.
$$
\det A \qquad \mathbb{K}^{N\times N}\to\mathbb{K}
$$
Uses the Leibniz formula.
TODO: Filter zero products.
Complexity
----------
There will be
- $N!-1$ scalar additions (`+`),
- $(N-1)N!$ scalar multiplications (`*`),
so $NN!-1$ arithmetic operations in total.
References
----------
[Wikipedia - Leibniz formula for determinants](https://en.wikipedia.org/wiki/Leibniz_formula_for_determinants)
"""
assert_sqmatrix(A)
def _det_leibniz(A:np.ndarray, progress:Progress) -> Any:
i:tuple[int,...] = tuple(range(A.shape[0]))
return progress.sum_default(
posneg(progress.prod_default(A[i, p]), s)
for p, s in _permutations(range(A.shape[0])))
if isinstance(progress, set):
totals = {
'+': factorial(A.shape[0])-1,
'*': (A.shape[0]-1)*factorial(A.shape[0])
}
with Progress({o:totals[o] for o in progress}, 'det_leibniz ') as progress:
return _det_leibniz(A, progress)
elif isinstance(progress, Progress):
return _det_leibniz(A, progress)
else:
raise TypeError('expected progress as `set` or `Progress`')
|