Trace and Determinant

Trace

If A is an n\times n square matrix with entries in a field F, then the trace \mathrm{trace}(A) is the sum \sum_{i=1}^{n} a_{ii} of the diagonal elements of A.

Proposition: If A and B are n\times n matrices over F, then \mathrm{trace}(AB)=\mathrm{trace}(BA).

Proof: Let C=AB and D=BA. Then c_{ij} = \sum_{k} a_{ik}b_{kj}.

and

d_{ij} = \sum_{k} b_{ik}a_{kj}

Now \mathrm{trace}(AB) = \sum_{i=1}^{n} c_{ii} = \sum_{i}\sum_{k} a_{ik}b_{ki} =\sum_{k}\sum_{i} b_{ki}a_{ik} =\sum_{k} d_{kk} = \mathrm{trace}(BA)

Trace of a linear map

Now let f:V\to V be any linear map, where V is a finite dimensional vector space. Choose a basis E for V and define the trace \mathrm{trace}(f) to be the trace of the matrix [f]_{E}^{E}.

This is a well-defined invariant of f because if we choose a different basis, say E', then [f]_{E'}^{E'} =[1]_{E'}^{E} [f]_{E}^{E}[1]_{E}^{E'} Thus \begin{aligned} \mathrm{trace}([f]_{E'}^{E'})&=\mathrm{trace}([1]_{E'}^{E}[f]_{E}^{E}[1]_{E}^{E'})\\ &=\mathrm{trace}([f]_{E}^{E}[1]_{E}^{E'}[1]_{E'}^{E})\\ &=\mathrm{trace}([f]_{E}^{E}) \end{aligned}

since [1]_{E'}^{E}[1]_{E}^{E'}=[1]_{E}^{E} is the identity matrix.

Trace, subspaces, and quotient spaces

Let V be a finite dimensional vector space and L:V\to V a linear map. Suppose that W is a subspace of V such that L(W)\subset W. Such a W is called an invariant subspace for L.

In this situation, the map L:V\to V gives rise to a well defined linear map \overline{L}:V/W\to V/W. This map is defined by L([v])=[L(v)]. It is well defined since, if we choose a different representative [v]=[v+w], then L([v+w]) = [L(v+w)] = [L(v)+L(w)] = [L(v)] since L(w)\in W.

Proposition: If W\subset V is an L-invariant subspace, let L_{W} be the restriction of L to W and let \overline{L} be the induced map V/W. Then \mathrm{trace}(L) = \mathrm{trace}(L_{W})+\mathrm{trace}(\overline{L})

We can state this in the language of complexes. Suppose X: 0\to A\to B\to C\to 0 is a short exact sequence of vector spaces and L=(L_1,L_2,L_3) is a linear map W\to W. In practice, this means we have a map L_2:B\to B whose restriction to A is L_1 and whose induced quotient map is L_3.

Then the trace of L satisfies: \mathrm{trace}(L) = \mathrm{trace}(L_1)-\mathrm{trace}(L_2)+\mathrm{trace}(L_3) = 0

Proof: Choose a basis for the subspace W and complete it to a basis E for all of V. Then the matrix [L]_{E}^{E} has an upper triangular block form [L]_{E}^{E} = \begin{pmatrix} L_1 & * \\ 0 & L_3 \end{pmatrix} The upper left block is the matrix of L restricted to W, and the lower right block is the matrix of the induced map in the basis [e_{i}] for the e_{i}\in E but not in W. Looking at the diagonal elements gives the result.

More generally, suppose that X^{\cdot} is a bounded complex of finite dimensional vector spaces and L is a linear map X^{\cdot}\to X^{\cdot}. Using the same ideas as for the proof of the dimension result for complexes, we have that the cocycles Z^{i}\subset X^{i} are an invariant subspace. Also, d_{i}(X^{i}/Z^{i})=B^{i+1} so we have a short exact sequence 0\to Z^{i}\to X^{i}\to B^{i+1}\to 0 and therefore \mathrm{trace}(L_{i}) = \mathrm{trace}(L_{Z^{i}}) + \mathrm{trace}(\overline{L}_{i})

If we define \mathrm{trace}(L|X^{\cdot}) = \sum (-1)^{i} \mathrm{trace}(L_{i})

then, by the same telescoping sum argument that we used when looking at the alternating sum of dimensions, we see that \mathrm{trace}(L|X^{\cdot}) = \sum (-1)^{i} \mathrm{trace}(\overline{L}_{i}) where the \overline{L}_{i} are the induced linear maps on cohomology.

Indeed, the dimension of a finite dimensional vector space (at least over a field of “characteristic zero”), is just the trace of the identity map, so the dimension result follows from this.

Determinant

Proposition: There is a unique function (the determinant) from M_n(F) to F satisfying the following properties:

  1. \det is multilinear as a function of the rows of A\in M_{n}(F). In other words, if we think of A as made up of n rows A_{1},\dots, A_{n} then \det(A) = \det(A_1,\ldots, A_n)

is linear in each of its variables separately. For each 1\le i\le n this means: \det(A_1,\ldots, A_{i}+B_{i},\ldots, A_n) = \det(A_1,\ldots, A_i,\ldots, A_n) + \det(A_1,\ldots, B_{i},\ldots, A_n)

and \det(A_1,\ldots, aA_{i},\ldots, A_n) = a\det(A_1,\ldots, A_{i},\ldots, A_{n}).

  1. The determinant function is alternating. This means that \det vanishes on any collection of rows A_1,\ldots, A_n where two rows are repeated. One consequence of this is that swapping any two rows changes the sign of the determinant. For example, since \det(A_1+A_2,A_1+A_2,\ldots, A_n) = 0 by linearity we get \begin{aligned} \det(A_1,A_1+A_2,\ldots, A_n) &+\det(A_2, A_1+A_2,\ldots, A_n) \\ &=\det(A_1,A_1,\ldots, A_n) + \det(A_1,A_2,\ldots, A_n) \\ &\quad+ \det(A_2,A_2,\ldots, A_n) + \det(A_2, A_1,\ldots, A_n) \\ &=0 \end{aligned}

This in turn means \det(A_1,A_2,\ldots, A_n) = -\det(A_2,A_1,\ldots, A_n).

  1. The determinant of the identity matrix is 1.

Proving the existence of such a function is kind of a pain in the neck, but we can make some observations that will help make sense of the situation.

Notice first that if the map exists, then the properties above tell us exactly how the elementary row operations affect it. In particular:

  1. If A is obtained from A' by interchanging two rows, then \det(A)=-\det(A'). This follows from the alternating property.

  2. If A is obtained from A' by multiplying a row by a scalar a, then \det(A)=a\det(A').

  3. If A is obtained from A' by adding a multiple of one row to another, then \det(A)=\det(A'). To see this note that \det(A_1+aA_i,A_2,\ldots, A_n) = \det(A_1,\ldots, A_n)+a\det(A_i,A_2,\ldots, A_i,\ldots, A_n)

and the second term in the sum on the right is zero by the alternating property.

We know that we can reduce an n\times n matrix A to row-reduced echelon form using elementary row operations, and by tracking the effect of those operations on \det(A) we see that it’s enough to know how to compute the determinant of a matrix A' which has k 1’s followed by n-k 0’s on the diagonal. If k=n, then this is the identity matrix so the determinant is 1. On the other hand, if the last row of A' is zero, then \det(A'_1,\ldots, A'_n) = \det(A'_1,\ldots, 0\cdot A'_n) = 0\cdot\det(A'_1,\ldots, A'_n) = 0

In other words, assuming the determinant exists, we have an algorithm to compute it.

To establish existence, notice first that for 1\times 1 matrices A=(a) the determinant is just a. For 2\times 2 matrices

A = \left[\begin{matrix} a & b \\ c & d\end{matrix}\right]

then the usual \det(A)=ad-bc has the desired properties.

We proceed inductively. Suppose A=(a_{ij}) is n\times n. Let A_{i} be the submatrix of A obtained by deleting the first row and the i^{th} column of A. This is an (n-1)\times (n-1) matrix so its determinant is known inductively. Define \det(A) = \sum_{i=1}^{n} (-1)^{i+1}a_{1i}\det(A_{i}).

This definition satisfies the linearity condition and takes the value 1 on the n\times n identity matrix. The tricky part is the alternating condition, and for that we only need to consider the case in which the first two rows of A are the same.

Now \det(A_{i}) = \sum_{j=1,j\not=i}^{n} (\pm)a_{2j}\det(A_{ij})

where A_{ij} is the matrix A with columns i and j deleted. Here we leave the sign unspecified – it’s the whole point, but we’ll figure it out shortly.

If we expand \det(A) in a double sum, the term \det(A_{ij}) appears twice: once with coefficient \pm a_{1i}a_{2j} and once with coefficient \pm a_{1j}a_{2i}. If we can show that these terms have opposite signs, then if the first two rows of A are equal the sum will cancel out and yield zero as desired.

The sign in front of a_{1i} is (-1)^{i+1}. The sign in front of a_{2j} depends on whether j is less than or greater than i. If less, it’s (-1)^{j+1}. If more, it’s (-1)^{j}.
(This is because when expanding the subdeterminant \det(A_{i}), skipping i changes the parity of the term associated with the index j.)

So the combined sign is \epsilon_{ij} = \begin{cases} (-1)^{i+j} & j<i \\ (-1)^{i+j+1} & j>i \end{cases}

The sign \epsilon_{ji} in front of a_{1j} is (-1)^{j+1} and that in front of a_{2i} is (-1)^{i+1} if i<j and (-1)^{i} if i>j. So \epsilon_{ji} = \begin{cases} (-1)^{i+j} & i<j \\ (-1)^{i+j+1} & i>j \end{cases}

Comparing these shows that in fact the signs are opposite.

Thus we have an inductive formula that yields the determinant.

For computational purposes, row reduction is much more efficient.

Proposition: The determinant is multiplicative: \det(AB)=\det(A)\det(B).

Proof: Recall that each of the row operations can be carried out by multiplication by an appropriate elementary matrix. The swapping matrices P_{ij} have determinant -1 and the “add a multiple of a row” matrices R_{ji}(\lambda) have determinant 1 – you can see this directly from the properties of the determinant. The scaling matrix D_{i}(\lambda) has determinant \lambda. So, for each of these matrices E, we have \det(EA)=\det(E)\det(A).

By row reduction any matrix A is a product of elementary matrices. If A=E_{1}\cdots E_{k} and B=F_{1}\cdots F_{l} where E_{i} and F_{j} are elementary matrices, then \det(AB)=\det(E_{1}\cdots E_{k}F_{1}\cdots F_{l})=\det(A)\det(B).

Corollary: A matrix is invertible if and only if its determinant is nonzero.

Proof: If A is invertible then we can find B so that AB=I and therefore \det(A)\det(B)=1 so \det(A) is nonzero. Conversely, if we write A=E_{1}\cdots E_{k}J

where the E_{i} are elementary matrices and J is diagonal, then \det(A)=0 if and only if \det(J)=0, which happens if and only if J has a zero on the diagonal. (Since J is in row-reduced echelon form, every diagonal entry is either 0 or a pivot, hence exactly 1.) So if \det(A) is nonzero, then J is the identity matrix, and one gets an inverse for A from the inverses of the E_{i}.

A few properties of the determinant

  1. The formula we used to define the determinant is called the “cofactor expansion” on the first row. One can use any row to get a similar expansion.

  2. One can use columns instead of rows.

  3. Let B=A^{adj} be the matrix where b_{ij} = (-1)^{i+j}\det(A_{ji})

where A_{ji} is the matrix obtained from A by deleting the j^{th} row and the i^{th} column. This matrix is called the (classical) adjoint or the adjugant of A.

Proposition: AA^{adj} = A^{adj}A = \det(A)I.

Proof: Let B=A^{adj} and C=AB. Then c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj} = \sum_{k=1}^{n} (-1)^{k+j} a_{ik}\det(A_{jk}) = (-1)^{j+1}\sum_{k=1}^{n} (-1)^{k+1}a_{ik}\det(A_{jk}).

If i and j are different, then row i of A is included in \det(A_{jk}) and so

\sum_{k=1}^{n} (-1)^{k+1}a_{ik}\det(A_{jk})

is the cofactor expansion of the determinant of the matrix obtained by replacing row j of A by a duplicate of row i and expanding along row j. This is zero since it’s the determinant of a matrix with a repeated row.

On the other hand, if i and j are equal, this is (-1)^{i+1}\sum_{k=1}^{n} (-1)^{k+1}a_{ik}\det(A_{ik}) which is \det(A).

Remark: We need to check the sign here: the cofactor expansion around row i gets a sign (-1)^{i+1}. This is because the cofactor expansion around row i satisfies the conditions characterizing the determinant except that it gives (-1)^{i+1} for the identity matrix.

Remark: This gives us an “explicit” formula for the inverse of A as \det(A)^{-1}A^{adj}.

Expansion of the determinant

If A\in M_{n}(F) and A_{i}=\sum a_{ij}e_{j} is the i^{th} row of A written in terms of the standard row vectors e_{i} having a 1 in position i and zeroes elsewhere, then in follows from the multilinearity of the determinant that we can write \det(A)=\det(A_1,\ldots, A_n) = \sum a_{1i_{1}}a_{2i_{2}}\cdots a_{ni_{n}}\det(e_{i_{1}},e_{i_{2}},\ldots, e_{i_{n}})

This is because any term with a repeated index will have zero determinant by the alternating property.

The determinant \det(e_{i_{1}},\ldots, e_{i_{n}}) is \pm 1.

If the determinant \det(e_{i_{1}},\ldots, e_{i_{n}}) is +1, we say that the permutation i_{1},\ldots, i_{n} is even; otherwise we say it’s odd.

Any permutation can be “sorted” into the 1,\ldots, n by a sequence of operations where you exchange two indices. For example, (2,4,1,3)\to(1,4,2,3)\to (1,2,4,3)\to (1,2,3,4).

Each such exchange reverses the sign of the permutation since it corresponds to an elementary row operation where you swap to rows.

So a permutation is even if it can be sorted by an even number of exchanges, and odd if it requires an odd number.

It’s not obvious from a combinatorial point of view that this is well-defined, but since we have an alternative formula via the determinant we can see that it is.

This expansion is essentially useless since it involves n! terms, each a product of n terms.

Cramer’s Rule

Suppose that A is an n\times n matrix over F and b\in F^{n}. We can look at the linear system of equations Ax = b. If \det(A)\not=0, we can “solve” this system by multiplying both sides by the adjugant matrix:

A^{adj}Ax=A^{adj}b

So x=\det(A)^{-1}A^{adj}b.

If we look more closely at A^{adj}b, we see that the j^{th} entry of A^{adj}b (corresponding to the value of x_{j} in x) is (A^{adj}b)_{j} = \sum_{i=1}^{n} A^{adj}_{ji}b_{i} = (-1)^{j+1}\sum_{i=1}^{n}(-1)^{i+1}\det(A_{ij})b_{i}

This expression is the cofactor expansion of the matrix A_{j}(b) obtained from A by replacing the j^{th} column with b.

This yields the formula (called “Cramer’s Rule”) x_{j} = \frac{\det(A_{j}(b))}{\det(A)}

Although not useful for calculation, it is worth observing that, as a consequence of Cramer’s rule, if A has integer entries, b has integer entries, and \det(A)=\pm 1, then the solution x to Ax=b also has integer entries.

Determinant of a Linear Map

Let f:V\to V be a linear map where V is a finite dimensional vector space over F. We define the determinant of f to be the determinant of [f]_{E}^{E} where E is any basis for V.

Since choosing a different basis E' changes the matrix A=[f]_{E}^{E} by similarity to a matrix B=PAP^{-1}, the determinant is independent of the choice of basis and is thus a well-defined invariant of f.

Determinants in complexes

Proposition: Suppose X: 0\to A_1\to A_2\to A_3\to 0 is a short exact sequence of finite dimensional vector spaces and L:X\to X is a linear map. So L=(L_1,L_2,L_3) where L_i:A_i\to A_i and the diagram: \begin{array}{ccccccccc} 0 & \to & A_1 & \to & A_2 & \to & A_3 & \to & 0 \\[4pt] & & \downarrow^{L_1} & & \downarrow^{L_2} & & \downarrow^{L_3} & & \\[4pt] 0 & \to & A_1 & \to & A_2 & \to & A_3 & \to & 0 \end{array}

commutes. Then \det(L_2) = \det(L_1)\det(L_3).

Proof: Choose a basis for A_1 and extend it to a basis E for A_2. As in the case with the trace, the matrix of L in this basis is block upper triangular. The upper left block is the matrix of L_1, and the lower right block is the matrix of L_3: [L]_{E}^{E} = \begin{pmatrix} [L_1] & * \ 0 & [L_3] \end{pmatrix} Using row operations, you can kill off the \* entries, and eventually see that the determinant of this matrix is \det([L_1])\det([L_3]).

More generally, using an alternating product, you can show that, given a bounded complex X^{\cdot} of finite dimensional vector spaces, and a linear map L:X^{\cdot}\to X^{\cdot}, that \sum (-1)^{i}\det(L^{i}:X^{i}\to X^{i}) = \sum (-1)^{i} \det(\overline{L}^{i}:H^{i}(X^{\cdot})\to H^{i}(X^{\cdot})) where the \overline{L}_{i} are the induced map on cohomology.