A Zephyr in Time: Determinants!

And now, finally, the post that everyone is waiting for: determinants.

Honestly, the person who defined determinants (in any one of several possible ways) must be more than just brilliant: that person must also be crazy. Well, I thought the definition was insane the first time I saw it, anyway. Given a matrix A with entries $a_{ij}$ , we define the determinant of the matrix as

$\begin{eqnarray*} \det(A) & = & |A|=\sum_{\sigma\in S_{n}}\mathrm{sgn}(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)}\end{eqnarray*}$

Looks ugly, but it is surprisingly neat to work with.

There are numerous theorems and properties that can be proven about determinants, but going through them all will require more time than my attention span can handle. Thus I will touch on what possibly are the most important two properties: multilinearity of matrix rows (or columns), and the alternating property.

First, multilinearity. Given that we are talking about linear algebra, it's kind of depressing that the function "find the determinant of a matrix" is not linear. That is, given $n\times n$ matrices A and B, scalar c, in most cases

$\det(cA+B)\not=c\det A+\det B$

Instead, we have something odder: multilinearity. It's kind of hard for me to speak intuitively about this, so I'll just jumps straight right in to the formal statement:

Let $\alpha_{i}$ denote the ith row of an $n\times n$ matrix $A=[a_{ij}]$ , such that we may write

$\begin{eqnarray*} A & = & \left[\begin{array}{c} \alpha_{1}\\ \vdots\\ \alpha_{n}\end{array}\right]\end{eqnarray*}$

Then the map

$\begin{eqnarray*} T_{k}:\mathbb{F}^{n} & \mapsto & \mathbb{F}\\ T_{k}\beta & = & \det\left[\begin{array}{c} \alpha_{1}\\ \vdots\\ \alpha_{k-1}\\ \beta\\ \alpha_{k+1}\\ \vdots\\ \alpha_{n}\end{array}\right]\end{eqnarray*}$

is linear.

For simplicity, here's the proof for k = 1 (the proof is practically the same for any k).

Suppose $\beta=(x_{1},\ldots,x_{n})$ . Then

$\begin{eqnarray*} \det\left[\begin{array}{c} \beta\\ \alpha_{2}\\ \vdots\\ \alpha_{n}\end{array}\right] & = & \sum_{\sigma\in S_{n}}x_{\sigma(1)}a_{2,\sigma(2)}\ldots a_{n,\sigma(n)}\\ & = & \sum_{\sigma\in S_{n}}x_{\sigma(1)}c_{\sigma}\end{eqnarray*}$

where $c_{\sigma}=a_{2,\sigma(2)}\ldots a_{n,\sigma(n)}$ is a product that is completely unrelated to $\beta$ . Now, we can "partition" $S_{n}$ into subsets where $\sigma(1)=1,2,\ldots,n$ respectively.
Then

$\begin{eqnarray*} \det\left[\begin{array}{c} \beta\\ \alpha_{2}\\ \vdots\\ \alpha_{n}\end{array}\right] & = & \sum_{j=1}^{n}x_{j}\left(\sum_{\sigma(1)=j}c_{\sigma}\right)\\ & = & \sum_{j=1}^{n}x_{j}t_{j}\end{eqnarray*}$

where $t_{j}={\displaystyle \sum_{\sigma(1)=j}c_{\sigma}}$ again is not related to $\beta$ . Now it is obvious that $T_{k}\beta$ is linear in $\beta$ : if $\beta_{1}=(x_{1},\ldots,x_{n})$ and $\beta_{2}=(y_{1},\ldots,y_{n})$ , and s is scalar, then

$\begin{eqnarray*} T_{k}(s\beta_{1}+\beta_{2}) & = & \sum_{j=1}^{n}(sx_{j}+y_{j})t_{j}\\ & = & s\sum_{j=1}^{n}x_{j}t_{j}+\sum_{j=1}^{n}y_{j}t_{j}\\ & = & sT_{k}\beta_{1}+T_{k}\beta_{2}\end{eqnarray*}$

I realize that I was kind of hand-wavy at the crux of the proof, but it's one of those "you'll get it if you stare at it long enough" things.

The alternating property is, in my opinion, less awkward to think about. There are two parts to the alternating property:

If two rows of A are identical, then $\det(A)=0$
If we interchange two rows of A to obtain B, then $\det(B)=-\det(A)$

Proof for part 1:

Suppose row 1 = row 2 (the argument is the same in general). Then

$\begin{eqnarray*} A & = & \left[\begin{array}{ccc} v_{1} & \ldots & v_{n}\\ v_{1} & \ldots & v_{n}\\ a_{31} & \ldots & a_{3n}\\ \vdots & \ddots & \vdots\\ a_{n1} & \ldots & a_{nn}\end{array}\right]\end{eqnarray*}$

$\begin{eqnarray*} \det(A) & = & \sum_{\sigma\in S_{n}}\mathrm{sgn}(\sigma)a_{1,\sigma(1)}a_{2,\sigma(2)}\ldots a_{n,\sigma(n)}\\ & = & \sum_{\sigma\in S_{n}}\mathrm{sgn}(\sigma)v_{\sigma(1)}v_{\sigma(2)}\ldots a_{n,\sigma(n)}\\ & = & \sum_{\sigma\,\textrm{even}}v_{\sigma(1)}\ldots a_{n,\sigma(n)}-\sum_{\sigma\textrm{ odd}}v_{\sigma(1)}\ldots a_{n,\sigma(n)}\end{eqnarray*}$

Let $A_{n}$ be the set of even permutations, and $\tau=\left(\begin{array}{cc} 1 & 2\end{array}\right)$ . Then

$\begin{eqnarray*} \det(A) & = & \sum_{\sigma\in A_{n}}v_{\sigma(1)}v_{\sigma(2)}\ldots a_{n,\sigma(n)}-\sum_{\sigma\in A_{n}}v_{\sigma\tau(1)}v_{\sigma\tau(2)}a_{3\sigma\tau(3)}\ldots a_{n,\sigma\tau(n)}\end{eqnarray*}$

since as $\sigma$ runs through all even permutations, $\sigma\tau$ runs through all odd permutations. Since $\tau(1)=2$ , $\tau(2)=1$ ,and $\tau(k)=k$ for all $k\not=1,2$ , we get

$\begin{eqnarray*} \det(A) & = & \sum_{\sigma\in A_{n}}v_{\sigma(1)}v_{\sigma(2)}\ldots a_{n,\sigma(n)}-\sum_{\sigma\in A_{n}}v_{\sigma(2)}v_{\sigma(1)}a_{3\sigma(3)}\ldots a_{n,\sigma(n)}\\ & = & 0\end{eqnarray*}$

Proof for part 2:

Suppose we interchange the first two rows to get B from A (as before, the argument
is the same for interchanging any other two rows). Say

$\begin{eqnarray*} A=\left[\begin{array}{c} \beta\\ \gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right] & & B=\left[\begin{array}{c} \gamma\\ \beta\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]\end{eqnarray*}$

Let $C=\left[\begin{array}{c} \beta+\gamma\\ \beta+\gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]$ . We know that $\det(C)=0$ from Part 1. Using multilinearity,

$\begin{eqnarray*} \det(C) & = & \det\left[\begin{array}{c} \beta+\gamma\\ \beta+\gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]=\det\left[\begin{array}{c} \beta\\ \beta+\gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]+\det\left[\begin{array}{c} \gamma\\ \beta+\gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]\\ 0 & = & \det\left[\begin{array}{c} \beta\\ \beta\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]+\det\left[\begin{array}{c} \beta\\ \gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]+\det\left[\begin{array}{c} \gamma\\ \beta\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]+\det\left[\begin{array}{c} \gamma\\ \gamma\\ \alpha_{3}\\ \vdots\\ \alpha_{n}\end{array}\right]\\ 0 & = & 0+\det(A)+\det(B)+0\\ \det(A) & = & -\det(B)\end{eqnarray*}$

And that, rather chaotically, ends my discussion on determinants. I should stress that there is much more to determinants than this. Determinants and invertibility! Laplacian expansion! Eigenvalue problems! Maybe I will blog about some of these topics as time goes on...

I should also take the time here to apologise to my algebra professor because I am snagging all his notation for his proofs, too.

[edited]
Where did all my pictures go? Fixing in progress... gah.

[edited again]
The LaTeX-transforming script doesn't seem to take spaces very gracefully. I might fix this tomorrow (or not) - a bit too blurry-eyed from too many $$'s...

3 comments:

Felix said...: so you americans think in row vectors rather than column vectors ... and F is the name for a general field (which makes sense I guess)
sorry, for a qualified comment i'd have to think it all through :), maybe I will; January 24, 2008 at 2:53 AM
Echiral said...: Hey! Canadian, not American. Nontrivial distinction, this.

And I am curious: if you don't refer to a field as F, what do you call it?; January 24, 2008 at 2:06 PM
Felix said...: Körper is abbreviated with K, I usually don't read these things in English :); January 25, 2008 at 12:23 PM

A Zephyr in Time

Wednesday, January 23, 2008

Determinants!

3 comments:

About Me

Chemists

Equivalence Classes and/in Academia

Coffee-Theorem Operators

\int dq/T