During AMC testing, the AoPS Wiki is in read-only mode. No edits can be made.

Difference between revisions of "Determinant"

(started article)
 
(determinants in terms of simpler determinants)
 
(2 intermediate revisions by one other user not shown)
Line 29: Line 29:
 
Our generalized determinants also satisfy the multiplicative property
 
Our generalized determinants also satisfy the multiplicative property
 
when <math>A</math> is [[associative]].
 
when <math>A</math> is [[associative]].
 +
 +
== Determinants in Terms of Simpler Determinants ==
 +
 +
An <math>n\times n</math> determinant can be written in terms of <math>(n-1)\times(n-1)</math> determinants:
 +
<cmath>\det(a_{n\times n})=\sum_{i=1}^n(-1)^{i+1}\det(m_i)</cmath>
 +
where <math>m_i</math> is the <math>(n-1)\times(n-1)</math> matrix formed by removing the <math>1</math>st row and <math>i</math>th column from <math>a</math>:
 +
<cmath>m_i=\begin{pmatrix}
 +
\blacksquare & \blacksquare & ... & \blacksquare & \blacksquare & \blacksquare & ... & \blacksquare & \blacksquare\\
 +
a_{21} & a_{22} & ... & a_{2,i-1} & \blacksquare & a_{2,i+1} & ... & a_{2,n-1} & a_{2n}\\
 +
a_{31} & a_{32} & ... & a_{3,i-1} & \blacksquare & a_{3,i+1} & ... & a_{3,n-1} & a_{3n}\\
 +
&&&&\vdots&&&&\\
 +
a_{n1} & a_{n2} & ... & a_{n,i-1} & \blacksquare & a_{n,i+1} & ... & a_{n,n-1} & a_{nn}
 +
\end{pmatrix}=\begin{pmatrix}
 +
a_{21} & ... & a_{2,i-1} & a_{2,i+1} & ... & a_{2n}\\
 +
a_{31} & ... & a_{3,i-1} & a_{3,i+1} & ... & a_{3n}\\
 +
&&\vdots&\vdots&&&\\
 +
a_{n1} & ... & a_{n,i-1} & a_{n,i+1} & ... & a_{nn}
 +
\end{pmatrix}</cmath>
 +
 +
This makes it easy to see why the determinant of an <math>n\times n</math> matrix <math>a</math> is the sum of the diagonals labeled <math>+</math>, minus the sum of the diagonals labeled <math>-</math>, where "diagonal" means the product of the terms along it:
 +
<center><asy>
 +
size(300);
 +
draw(arc((3.3,-1.5), 4, 155, 205));
 +
draw(arc((-0.3,-1.5), 4, -25, 25));
 +
label("$a_{11}$",(0,0));
 +
label("$a_{12}$",(1,0));
 +
label("$...$",(2,0));
 +
label("$a_{1n}$",(3,0));
 +
 +
label("$a_{21}$",(0,-1));
 +
label("$a_{22}$",(1,-1));
 +
label("$...$",(2,-1));
 +
label("$a_{2n}$",(3,-1));
 +
 +
label("$\vdots$",(0,-2));
 +
label("$\ddots$",(2,-2));
 +
 +
label("$a_{n1}$",(0,-3));
 +
label("$a_{n2}$",(1,-3));
 +
label("$...$",(2,-3));
 +
label("$a_{nn}$",(3,-3));
 +
label("$a_{11}$",(0,0));
 +
label("$a_{12}$",(1,0));
 +
label("$...$",(2,0));
 +
label("$a_{1n}$",(3,0));
 +
 +
 +
label("$a_{11}$",(4,0));
 +
label("$a_{12}$",(5,0));
 +
label("$...$",(6,0));
 +
label("$a_{1n}$",(7,0));
 +
 +
label("$a_{21}$",(4,-1));
 +
label("$a_{22}$",(5,-1));
 +
label("$...$",(6,-1));
 +
label("$a_{2n}$",(7,-1));
 +
 +
label("$\vdots$",(4,-2));
 +
label("$\ddots$",(6,-2));
 +
 +
label("$a_{n1}$",(4,-3));
 +
label("$a_{n2}$",(5,-3));
 +
label("$...$",(6,-3));
 +
label("$a_{nn}$",(7,-3));
 +
 +
for (int i=0; i<4; ++i)
 +
{
 +
draw((i-0.2,0.2)--(i+3-0.2,-3+0.2));
 +
label("$+$",(i-0.4,0.4));
 +
}
 +
for (int i=0; i<4; ++i)
 +
{
 +
draw((i+0.2+4,0.2)--(i-3+4+0.2,-3+0.2));
 +
label("$-$",(i+0.4+4,0.4));
 +
}
 +
</asy></center>
  
 
== Matrix Determinants are Multiplicative ==
 
== Matrix Determinants are Multiplicative ==

Latest revision as of 23:31, 8 May 2020

The determinant is an important notion in linear algebra.

For an $n\times n$ matrix $a = (a_{ij})$, the determinant is defined by the sum \begin{align*} \det a &= \sum_{\sigma \in S_n} \text{sign} (\sigma) a_{1\sigma(1)} a_{2\sigma(2)} \dotsc a_{n\sigma(n)} \\ &= \sum_{\sigma \in S_n} \text{sign}(\sigma) \prod_{i=1}^n a_{i\sigma(i)} , \end{align*} where $S_n$ is the set of all permutations on the set $\{ 1, \dotsc, n\}$, and $\text{sign}(\sigma)$ is the parity of the permutation $\sigma$.

For example, the determinant of a $2\times 2$ matrix $\begin{pmatrix} a&b \\c&d \end{pmatrix}$ is $ad - bc$.

This quantity may seem unwieldy, but surprisingly, it is multiplicative. That is, for any $n \times n$ matrices $a,b$ (over the same commutative field), \[\det (ab) = \det (a) \cdot \det (b) .\]

More generally, if $F$ is a commutative field and $a$ is an element of a (strictly power associative) $n$-dimensional $F$-algebra $A$, then the determinant of $a$ is $(-1)^n$ times the constant term of the characteristic polynomial of $a$.

Our generalized determinants also satisfy the multiplicative property when $A$ is associative.

Determinants in Terms of Simpler Determinants

An $n\times n$ determinant can be written in terms of $(n-1)\times(n-1)$ determinants: \[\det(a_{n\times n})=\sum_{i=1}^n(-1)^{i+1}\det(m_i)\] where $m_i$ is the $(n-1)\times(n-1)$ matrix formed by removing the $1$st row and $i$th column from $a$: \[m_i=\begin{pmatrix} \blacksquare & \blacksquare & ... & \blacksquare & \blacksquare & \blacksquare & ... & \blacksquare & \blacksquare\\ a_{21} & a_{22} & ... & a_{2,i-1} & \blacksquare & a_{2,i+1} & ... & a_{2,n-1} & a_{2n}\\ a_{31} & a_{32} & ... & a_{3,i-1} & \blacksquare & a_{3,i+1} & ... & a_{3,n-1} & a_{3n}\\ &&&&\vdots&&&&\\ a_{n1} & a_{n2} & ... & a_{n,i-1} & \blacksquare & a_{n,i+1} & ... & a_{n,n-1} & a_{nn} \end{pmatrix}=\begin{pmatrix} a_{21} & ... & a_{2,i-1} & a_{2,i+1} & ... & a_{2n}\\ a_{31} & ... & a_{3,i-1} & a_{3,i+1} & ... & a_{3n}\\ &&\vdots&\vdots&&&\\ a_{n1} & ... & a_{n,i-1} & a_{n,i+1} & ... & a_{nn} \end{pmatrix}\]

This makes it easy to see why the determinant of an $n\times n$ matrix $a$ is the sum of the diagonals labeled $+$, minus the sum of the diagonals labeled $-$, where "diagonal" means the product of the terms along it:

[asy] size(300); draw(arc((3.3,-1.5), 4, 155, 205)); draw(arc((-0.3,-1.5), 4, -25, 25)); label("$a_{11}$",(0,0)); label("$a_{12}$",(1,0)); label("$...$",(2,0)); label("$a_{1n}$",(3,0));  label("$a_{21}$",(0,-1)); label("$a_{22}$",(1,-1)); label("$...$",(2,-1)); label("$a_{2n}$",(3,-1));  label("$\vdots$",(0,-2)); label("$\ddots$",(2,-2));  label("$a_{n1}$",(0,-3)); label("$a_{n2}$",(1,-3)); label("$...$",(2,-3)); label("$a_{nn}$",(3,-3)); label("$a_{11}$",(0,0)); label("$a_{12}$",(1,0)); label("$...$",(2,0)); label("$a_{1n}$",(3,0));   label("$a_{11}$",(4,0)); label("$a_{12}$",(5,0)); label("$...$",(6,0)); label("$a_{1n}$",(7,0));  label("$a_{21}$",(4,-1)); label("$a_{22}$",(5,-1)); label("$...$",(6,-1)); label("$a_{2n}$",(7,-1));  label("$\vdots$",(4,-2)); label("$\ddots$",(6,-2));  label("$a_{n1}$",(4,-3)); label("$a_{n2}$",(5,-3)); label("$...$",(6,-3)); label("$a_{nn}$",(7,-3));  for (int i=0; i<4; ++i) { draw((i-0.2,0.2)--(i+3-0.2,-3+0.2)); label("$+$",(i-0.4,0.4)); } for (int i=0; i<4; ++i) { draw((i+0.2+4,0.2)--(i-3+4+0.2,-3+0.2)); label("$-$",(i+0.4+4,0.4)); } [/asy]

Matrix Determinants are Multiplicative

In this section we prove that the determinant as defined for $n\times n$ matrices is multiplicative.

We first note that \begin{align*} \det a \det b &= \sum_{\sigma \in S_n} (-1)^{\sigma} 	\prod_{i=1}^n a_{i\sigma(i)} 	\sum_{\tau \in S_n} (-1)^{\tau} \prod_{j=1}^n b_{j\tau(j)} \\ &= \sum_{\sigma, \tau \in S_n} (-1)^{\tau \sigma} 	\prod_{i=1}^n a_{i\sigma(i)} \cdot \prod_{j=1}^n b_{\sigma(j) 	\tau (\sigma(j))} \\ &= \sum_{\sigma, \tau \in S_n} (-1)^{\tau \sigma} 	\prod_{i=1}^n a_{i \sigma(i)} b_{\sigma(i) \tau\circ \sigma(i)} , \end{align*} from rearrangements of terms. If we let $\upsilon = \tau \circ \sigma$, we then have \begin{align} \nonumber \det a \det b &= \sum_{\upsilon \in S_n} (-1)^\upsilon 	\sum_{\sigma \in S_n} \prod_{i=1}^n a_{i\sigma(i)} b_{\sigma(i) 	\upsilon(i)} \\ &= \sum_{\sigma \in S_n} \sum_{\upsilon \in S_n} (-1)^\upsilon 	\prod_{i=1}^n a_{i\sigma(i)} b_{\sigma(i) \upsilon(i)} . \end{align}

On the other hand, \begin{align*} \det ab &= \sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n (ab)_{i 	\upsilon(i)} \\ &= \sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n \sum_{j=1}^n 	a_{ij} b_{j \upsilon(i)} \\ &= \sum_{\upsilon \in S_n} (-1)^\upsilon \sum_{\phi \in [n]^{[n]}} 	\prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} \\ &= \sum_{\phi \in [n]^{[n]}} \sum_{\upsilon \in S_n} (-1)^\upsilon 	\prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} , \end{align*} where $[n]$ is the set $\{1, \dotsc, n\}$, and $[n]^{[n]}$ is the set of functions mapping $[n]$ into itself.

From equation (1), it thus suffices to show that if $\phi \in [n]^{[n]}$ is not a permutation on $[n]$, then \[\sum_{\upsilon \in S_n} (-1)^\upsilon \prod_{i=1}^n 	a_{i\phi(i)} b_{\phi(i) \upsilon(i)} = 0 . \qquad (2)\]

To this end, suppose that $\phi$ is not a permutation. Then there exist distinct integers $a,b \in [n]$ such that $\phi(a) = \phi(b)$. Let $\psi$ be the permutation on $[n]$ that transposes $a$ and $b$ while fixing everything else. Then \[\prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} 	= \prod_{i=1}^n a_{i\phi(i)} b_{\phi(i) \upsilon(\psi(i))} ,\] as the latter product is the same as the former, with two terms switched. On the other hand $\psi$ is an odd permutation, so \[(-1)^\upsilon \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(i)} + (-1)^{\upsilon \psi} \prod_{i=1}^n a_{i \phi(i)} b_{\phi(i) \upsilon(\psi(i))} =0 .\] Since $\psi = \psi^{-1}$, we can partition the elements of $S_n$ into pairs $\{ \sigma, \sigma \circ \tau\}$ for which the equation above holds. Equation 2 then follows, and we are done. $\blacksquare$

Equivalence of Definitions

We now prove that our two definitions are equivalent. We first note that the definitions coincide in the case of upper-triangular matrices, as each entry in the diagonal of an upper-triangular matrix corresponds to a (generalized) eigenvalue of the matrix.

We now use the fact that every element $a$ of $M_n(F)$ is similar to an upper triangular matrix; that is, there exists an upper triangular matrix $b$ and an invertible matrix $c$ such that \[a = c b c^{-1} .\] Writing $\det\nolimits'$ for our specialized determinant for matrices and $\det$ for our generalized definition with the characteristic polynomial, we have \begin{align*} \det\nolimits'(a) = \det\nolimits'(cbc^{-1}) &= \det\nolimits'(c) \cdot \det\nolimits'(bc^{-1}) \\ &= \det\nolimits'(bc^{-1}) \det\nolimits'(c) \\ &= \det\nolimits'(b) = \det b = \det a , \end{align*} as the characteristic polynomial does not change under automorphisms of $A$ that fix $F$. Our two definitions are therefore equivalent. $\blacksquare$

References

  • Garibaldi, Skip, "The Characteristic Polynomial and Determinant Are Not Ad Hoc Constructions". American Mathematical Monthly 111 (2004), no. 9, p. 761, Nov. 2004. Preprint

See also

Invalid username
Login to AoPS