en>Cydebot: Robot - Moving category Distributed data sharing to Distributed data storage per CFD at Wikipedia:Categories for discussion/Log/2009 December 2.

2009-12-10T08:26:55Z

Robot - Moving category Distributed data sharing to Distributed data storage per CFD at Wikipedia:Categories for discussion/Log/2009 December 2.

New page

In [[algebra]], the '''Leibniz formula''' expresses the [[determinant]] of a [[square matrix]]
:<math>A = (a_{ij})_{i,j = 1, \dots, n}</math>

in terms of permutations of the matrix elements. Named in honor of [[Gottfried Leibniz]], the formula is
:<math>\det(A) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i}</math>

for an ''n''×''n'' matrix, where sgn is the [[Even_and_odd_permutations|sign function]] of [[permutation]]s in the [[permutation group]] ''S''<sub>''n''</sub>, which returns +1 and −1 for [[even and odd permutations]], respectively.

Another common notation used for the formula is in terms of the [[Levi-Civita symbol]] and makes use of the [[Einstein summation notation]], where it becomes
:<math>\det(A)=\epsilon^{i_1\cdots i_n}{a}_{1i_1}\cdots {a}_{ni_n},</math>
which may be more familiar to physicists.

Directly evaluating the Leibniz formula from the definition requires <math>\Omega(n! \cdot n)</math> operations in general—that is, a number of operations asymptotically proportional to ''n'' [[factorial]]—because ''n''! is the number of order-''n'' permutations. This is impractically difficult for large ''n''. Instead, the determinant can be evaluated in O(''n''<sup>3</sup>) operations by forming the [[LU decomposition]] <math>A = LU</math> (typically via [[Gaussian elimination]] or similar methods), in which case <math>\det A = (\det L) (\det U)</math> and the determinants of the triangular matrices ''L'' and ''U'' are simply the products of their diagonal entries. (In practical applications of numerical linear algebra, however, explicit computation of the determinant is rarely required.) See, for example, Trefethen and Bau (1997).

== Formal statement and proof ==

'''Theorem.'''
There exists exactly one function
:<math> F : M_n (\mathbb K) \rightarrow \mathbb K </math>
which is [[Alternatization|alternate]] [[Multilinear_map|multilinear]] w.r.t. columns and such that <math>F(I) = 1</math>.

'''Proof.'''

'''Uniqueness:''' Let <math>F</math> be such a function, and let <math>A = (a_i^j)_{i = 1, \dots, n}^{j = 1, \dots , n}</math> be an <math>n \times n</math> matrix. Call <math>A^j</math> the <math>j</math>-th column of <math>A</math>, i.e. <math>A^j = (a_i^j)_{i = 1, \dots , n}</math>, so that <math>A = \left(A^1, \dots, A^n\right).</math>

Also, let <math>E^k</math> denote the <math>k</math>-th column vector of the identity matrix.

Now one writes each of the <math>A^j</math>'s in terms of the <math>E^k</math>, i.e.

:<math>A^j = \sum_{k = 1}^n a_k^j E^k</math>.

As <math>F</math> is multilinear, one has

:<math>
\begin{align}
F(A)& = F\left(\sum_{k_1 = 1}^n a_{k_1}^1 E^{k_1}, \dots, \sum_{k_n = 1}^n a_{k_n}^n E^{k_n}\right)\\
& = \sum_{k_1, \dots, k_n = 1}^n \left(\prod_{i = 1}^n a_{k_i}^i\right) F\left(E^{k_1}, \dots, E^{k_n}\right).
\end{align}
</math>

From alternation it follows that any term with repeated indices is zero. The sum can therefore be restricted to tuples with non-repeating indices, i.e. permutations:

:<math>F(A) = \sum_{\sigma \in S_n} \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(E^{\sigma(1)}, \dots , E^{\sigma(n)}).</math>

Because F is alternating, the columns <math>E</math> can be swapped until it becomes the identity. The [[Even_and_odd_permutations|sign function]] <math>\sgn(\sigma)</math> is defined to count the number of swaps necessary and account for the resulting sign change. One finally gets:

:<math>
\begin{align}
F(A)& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1}^n a_{\sigma(i)}^i\right) F(I)\\
& = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i
\end{align}
</math>

as <math>F(I)</math> is required to be equal to <math>1</math>.

Therefore no function besides the function defined by the Leibniz Formula is a multilinear alternating function with <math>F\left(I\right)=1</math>.

'''Existence:''' We now show that F, where F is the function defined by the Leibniz formula, has these three properties.

[[Multilinear]]:
:<math>
\begin{align}
F(A^1, \dots, cA^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma) ca_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
& = c \sum_{\sigma \in S_n} \sgn(\sigma) a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
&=c F(A^1, \dots, A^j, \dots)\\
\\
F(A^1, \dots, b+A^j, \dots) & = \sum_{\sigma \in S_n} \sgn(\sigma)\left(b_{\sigma(j)} + a_{\sigma(j)}^j\right)\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\\
& = \sum_{\sigma \in S_n} \sgn(\sigma)
\left( \left(b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right) + \left(a_{\sigma(j)}^j\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right)\right)\\
& = \left(\sum_{\sigma \in S_n} \sgn(\sigma) b_{\sigma(j)}\prod_{i = 1, i \neq j}^n a_{\sigma(i)}^i\right)
+ \left(\sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i)}^i\right)\\
&= F(A^1, \dots, b, \dots) + F(A^1, \dots, A^j, \dots)\\
\\
\end{align}
</math>
[[Alternating]]:
:<math>
\begin{align}
F(\dots, A^{j_1}, \dots, A^{j_2}, \dots)
& = \sum_{\sigma \in S_n} \sgn(\sigma) \left(\prod_{i = 1, i \neq j_1, i\neq j_2}^n a_{\sigma(i)}^i\right) a_{\sigma(j_1)}^{j_1} a_{\sigma(j_2)}^{j_2}\\
\end{align}
</math>
For any <math>\sigma \in S_n</math> let <math>\sigma'</math> be the tuple equal to <math>\sigma</math> with the <math>j_1</math> and <math>j_2</math> indices switched.
:<math>
\begin{align}
F(A) & = \sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}+\sgn(\sigma')\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma'(i)}^{i}\right)a_{\sigma'(j_{1})}^{j_{1}}a_{\sigma'(j_{2})}^{j_{2}}\right]\\
& =\sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\left[\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)a_{\sigma(j_{2})}^{j_{1}}a_{\sigma(j_{1})}^{j_{2}}\right]\\
& =\sum_{\sigma\in S_{n},\sigma(j_{1})<\sigma(j_{2})}\sgn(\sigma)\left(\prod_{i = 1, i \neq j_1, i\neq j_2}^na_{\sigma(i)}^{i}\right)\left(a_{\sigma(j_{1})}^{j_{1}}a_{\sigma(j_{2})}^{j_{2}}-a_{\sigma(j_{1})}^{j_{2}}a_{\sigma(j_{2})}^{j_{_{1}}}\right)\\
\\
\end{align}
</math>
Thus if <math>A^{j_1} = A^{j_2}</math> then <math>F(\dots, A^{j_1}, \dots, A^{j_2}, \dots)=0</math>.

Finally, <math>F(I)=1</math>:
:<math>
\begin{align}\\
F(I) & = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n I_{\sigma(i)}^i\\
& = \sum_{\sigma = (1,2,\dots,n)} \prod_{i = 1}^n I_{i}^i\\
& = 1
\end{align}
</math>

Thus the only functions which are multilinear alternating with <math>F(I)=1</math> are restricted to the function defined by the Leibniz formula, and it in fact also has these three properties. Hence the determinant can be defined as the only function

:<math> \det : M_n (\mathbb K) \rightarrow \mathbb K </math>

with these three properties.

==See also==
* [[Matrix (mathematics)|Matrix]]
* [[Laplace expansion]]
* [[Cramer's rule]]

==References==
*{{SpringerEOM|title=Determinant|id=Determinant&oldid=12692}}
* Lloyd N. Trefethen and David Bau, ''Numerical Linear Algebra'' (SIAM, 1997) ISBN 978-0898713619

[[Category:Determinants]]
[[Category:Gottfried Leibniz]]
[[Category:Linear algebra]]
[[Category:Articles containing proofs]]

Tulip Overlay - Revision history

en>Cydebot: Robot - Moving category Distributed data sharing to Distributed data storage per CFD at Wikipedia:Categories for discussion/Log/2009 December 2.