On the determinant of the product of two square matrices

On the determinant of the product of two square matrices

On one level, this note deals with the determinants of square matrices and their product and is about a proof of the theorem that the determinant of a product equals the product of the determinants of the factors. On another level, this note is about notation, and it is the latter issue that I shall address first.

In contrast to my current habits, I shall use sub- and superscripts, and shall even do so in a nested fashion when the need arises. Also, multiplication will be denoted by juxtaposition.

I assume that the reader is willing to recognize in

$$ \langle \sum i: 0 \leq i < n: A _ {i} B ^ {i} \rangle $$

the sum of n products of an A and a B each. Suppose now, that we have to deal with many of such sums, but all with the same range for the dummy. (This is, for instance, a very common situation in

geometrical considerations, in which the above n equals the number of dimensions of the space in question.) In that situation it pays to state the range once and for all, and not to repeat it in each summation. The above expression can then be ab- breviated to

$$ \langle \Sigma i: A _ {i} B ^ {i} \rangle $$

(I have adopted the habit of maintaining both colons as an indication that the range is implicitly understood.)

In the above, the variable i is declared to be the dummy by its occurrence after $\sum$ , but there are other ways of identifying the dummy. In what is known as "the Einstein convention", which is tailored to the summation of products, the above is abbreviated to

$$ A _ {i} B ^ {i} $$

where the dummy $i$ is identified as such by the fact that it occurs once as subscript of a factor of the product and once as superscript. This convention not only eliminates the " $\sum i\because$ ", but also the scoping parenthesis pair $\left| \langle \rangle \right|$ .

When I was introduced to the Einstein convention, no one mentioned the elimination of the scoping parentheses, for they had not been introduced yet: people would just write

$$ \sum_ {i} A _ {i} B ^ {i} + C $$

without making explicit the convention that would disambiguate the above.

Similarly, the identification of the dummy by its "double occurrence" raises the question "double occurrence where?". For instance, would summation be implied in

$$ A _ {i} + B ^ {i} \quad ? $$

Since, in all their applications, dimensional considerations would rule out formulae like the above, the physicists of those days did not bother.

We, however, live in different times, and state explicitly that summation is implied by the double occurrence, once as subscript and once as superscript of factors of the same product, which is then the term to be summed.

We would like to point out that the omission of the scoping parentheses is

justified by the observation of

$$ \langle \Sigma i: A _ {i} B ^ {i} \rangle \langle \Sigma j: C _ {j} D ^ {j} \rangle = \langle \Sigma i _ {2} j: A _ {i} B ^ {i} C _ {j} D ^ {j} \rangle , $$

an equality which is a consequence of the fact that multiplication distributes over addition. With the Einstein convention -and the As, B5, Cs and Ds being real or complex- the above expression is written

$$ A _ {i} B ^ {i} C _ {j} D ^ {j} \quad o r \quad A _ {i} C _ {j} B ^ {i} D ^ {j} $$

or any other of the 24 permutations. The omission of parentheses usually reflects the associativity of an (infix) operator; in the case of the Einstein convention, the omission of the parentheses also subsumes a distribution law.

For various reasons I shall introduce and explain my next notational convention in terms of a most classical notation, in fact the notation which was deemed respectable (and in which I was educated) half a century ago.

In the following, $A$ and $B$ are $n \times n$ matrices with real or complex elements. Their rows and their columns are indexed

from 1 through n . The element in row

and similarly for the elements of matrix B. (The purpose of the underlining will become clear in a moment.) Identifiers $h,i,j,k,l$ will be used to denote index vectors of length $n$ and the elements of $h$ are denoted by

$$ h _ {1} h _ {2} \dots h _ {n}, $$

and similarly for $i,j,k$ and $l$ . The individual indices in the above enumeration have a range from 1 through n.

Our new convention gives a meaning to $A_{i}^{j}$ - note that both sub- and superscripts are vectors; $A_{i}^{j}$ stands for a product of n elements of matrix A, to be precise

$$ (0) \quad A _ {i} ^ {j} = \underline {{A}} _ {i _ {1}} ^ {j _ {1}} \underline {{A}} _ {i _ {2}} ^ {j _ {2}} \dots \underline {{A}} _ {i _ {n}} ^ {j _ {n}} $$

Denoting the matrix product by an

$$ \mathrm {L e m m a 0} \quad (A \cdot B) _ {i} ^ {j} = A _ {i} ^ {k} B _ {k} ^ {j} $$

Proof We observe

$$ (A \cdot B) _ {i} ^ {j} $$

$$ = {\text {e x p a n s i o n o f i n d e x v e c t o r s} } $$

$$ (\underline {{A \cdot B}}) _ {i _ {1}} ^ {j _ {1}} (\underline {{A \cdot B}}) _ {i _ {2}} ^ {j _ {2}} \dots (\underline {{A \cdot B}}) _ {i _ {n}} ^ {j _ {n}} $$

$$ = {\mathrm {c l e f i n i t i o n o f m a t r i x p r o d u c t} } $$

$$ (\underline {{A}} _ {i _ {1}} ^ {k _ {1}} \underline {{B}} _ {k _ {1}} ^ {j _ {1}}) (\underline {{A}} _ {i _ {2}} ^ {k _ {2}} \underline {{B}} _ {k _ {2}} ^ {j _ {2}}) \dots (\underline {{A}} _ {i _ {n}} ^ {k _ {n}} \underline {{B}} _ {k _ {n}} ^ {j _ {n}}) $$

$$ = {\mathrm {c o m p l e x m u l t i p l i c a t i o n i s c o m m u t a t i v e} } $$

$$ (\underline {{A}} _ {i _ {1}} ^ {k _ {1}} \underline {{A}} _ {i _ {2}} ^ {k _ {2}} \dots \underline {{A}} _ {i _ {n}} ^ {k _ {n}}) (\underline {{B}} _ {k _ {1}} ^ {j _ {1}} \underline {{B}} _ {k _ {2}} ^ {j _ {2}} \dots \underline {{B}} _ {k _ {n}} ^ {j _ {n}}) $$

$$ = {\mathrm {c o n t r a c t i o n o f i n d e x v e c t o r s} } $$

$$ A _ {i} ^ {k} B _ {k} ^ {j} $$

$$ (E n d o f P r o o f) $$

Next we define for each $i$ the two constants $\varepsilon_{i}$ and $\varepsilon^{i}$ ; since for all $i$

$$ \varepsilon_ {i} = \varepsilon^ {i} $$

we need to define only one of them. With

$$ n a t = 1 2 \dots n $$

we have

$$ \begin{array}{l} \varepsilon_ {i} = 0 \quad \mathrm {i f} i \mathrm {i s n o t a p e r m u t a t i o n o f n a t} (\mathrm {i n w h i c h c a s e} i \mathrm {c o n t a i n s a t l e a s t}) \ \begin{array}{l l} {\varepsilon_ {i} = + 1} & {\mathrm {i f} i \mathrm {i s a n e v e n p e r m u t a t i o n o f n a t}} \ {\varepsilon_ {i} = - 1} & {\mathrm {i f} i \mathrm {i s a n o d d p e r m u t a t i o n o f n a t}} \end{array} \ \end{array} $$

Without taking into account when per mutations are even or odd, the above implies

$$ \mathrm {L e m m a 1} \quad \varepsilon_ {i} \varepsilon^ {i} = n! $$

because distinct objects admit n! distinct sequential arrangements.

Let for the sake of the following dis- cussion, the operator be associated with two positions in index vectors and clense the interchange of the elements in those two positions. Since the interchange of two elements turns an even permutation into an odd one and vice versa, $\varepsilon$ satisfies

$$ \varepsilon^ {i} = - \varepsilon^ {i ^ {\prime}} \tag {1} $$

We now observe

$$ \begin{array}{l} \varepsilon^ {i} A _ {i} ^ {j} \ = \quad \left{i \text {r a n g e s o v e r a l l} n ^ {n} \text {p o s s i b l e} \right. \ \varepsilon^ {i ^ {\prime}} A _ {i ^ {\prime}} ^ {j} \ \end{array} $$

$$ \begin{array}{l} = {\varepsilon^ {i ^ {\prime}} = - \varepsilon^ {i}, \mathrm {s e e} (1); A _ {i ^ {\prime}} ^ {j} = A _ {i} ^ {j ^ {\prime}}, \mathrm {s e e} (0) } \ - \varepsilon^ {i} A _ {i} ^ {j ^ {\prime}} \ \end{array} $$

i.e. we have established

$$ \varepsilon^ {i} A _ {i} ^ {j} = - \varepsilon^ {i} A _ {i} ^ {j ^ {\prime}} $$

From (1) and (2) we establish

$$ \mathrm {L e m m a 2} \qquad \varepsilon^ {i} A _ {i} ^ {k} \varepsilon^ {l} = \varepsilon^ {i} A _ {i} ^ {e} \varepsilon^ {k} $$

Proof On account of (2) and (1), the transformation of $\varepsilon^i A_i^k$ to $\varepsilon^i A_i^\ell$ into- duces as many sign changes as the trans- formation from $\varepsilon^{\ell}$ to $\varepsilon^k$ , so they cancel. (End of Proof.)

The traditional definition of Det. $A$ , i.e., "the determinant of $A$ ",is

$$ (3) \quad D e f. A = \varepsilon^ {i} A _ {i} ^ {n a t} $$

but I prefer the more symmetric

$$ \mathrm {D e t .} A = \varepsilon^ {i} A _ {i} ^ {j} \varepsilon_ {j} / n! \tag {4} $$

The equivalence of these two definitions depends on

$$ (5) \quad \varepsilon^ {n a t} = + 1, $$

which enables us to derive:

$$ \varepsilon^ {i} A _ {i} ^ {n a t} $$

$$ \begin{array}{l} = {\mathrm {L e m m a} 1 } \ \varepsilon^ {i} A _ {i} ^ {n a t} \varepsilon^ {j} \varepsilon_ {j} / n! \ = {\mathrm {L e m m a} 2 } \ \varepsilon^ {i} A _ {i} ^ {j} \varepsilon^ {n a t} \varepsilon_ {j} / n! \ = {5 } \ \varepsilon^ {i} A _ {i} ^ {j} \varepsilon_ {j} / n! \ \end{array} $$

from which observation the equivalence of (3) and (4) follows.

And now we are ready to prove this note's main theorem.

$$ \begin{array}{l} \mathrm {T h e o r e m} \quad \mathrm {D e t .} (A \bullet B) = (\mathrm {D e t .} A) (\mathrm {D e t .} B) \ \mathrm {P r o o f} \quad \mathrm {W e o b s e r v e} \ D e t. (A \cdot B) \ = {(4) } \ \end{array} $$

$$ \begin{array}{l} \varepsilon^ {i} (A \cdot B) _ {i} ^ {j} \varepsilon_ {j} / n! \ = {\mathrm {L e m m a} 0 } \ \varepsilon^ {i} A _ {i} ^ {k} B _ {k} ^ {j} \varepsilon_ {j} / n! \ = {\text {L e m m a} 1 } \ \varepsilon^ {i} A _ {i} ^ {k} \varepsilon^ {\ell} \varepsilon_ {\ell} B _ {k} ^ {j} \varepsilon_ {j} / (n!) ^ {2} \ = {\mathrm {L e m m a} 2 } \ \varepsilon^ {i} A _ {i} ^ {\ell} \varepsilon^ {k} \varepsilon_ {e} B _ {k} ^ {j} \varepsilon_ {j} / (n!) ^ {2} \ = {\text {r e g r o u p i n g} } \ (\varepsilon^ {i} A _ {i} ^ {\ell} \varepsilon_ {e} / n!) (\varepsilon^ {k} B _ {k} ^ {j} \varepsilon_ {j} / n!) \ = {(4), + w i c e } \ (\mathrm {D e t .} A) (\mathrm {D e t .} B) \ \end{array} $$

(End of Proof)

￥

Matrix theory is closely associated with linear transformation of $n$ -dimensional space, the functional composition of two transformations corresponding to the scalar product of their matrices. Since the determinant of the matrix equals the factor by which the transformation expands the n-dimensional volume, linear transformations provide a model in which our theorem is

"obvious".

The above is essentially the proof I constructed as a young student. (for once I had been dis-satisfied with what my master Prof. J. Haantjes, had presented.) At the time my calculations took much more paper: firstly I did not know the Einstein convention, secondly I used without shame or hesitation subscripted dummies and the "... as I have done here in definition (0) and the proof of Lemma (0).

But as soon as one considers subscription as a notational alternative for function application, the "subscripted dummy" becomes an anomaly, for dummies should be "fresh variables" or "fresh identifiers" and not func tion values. Instead of considering

$$ h _ {1} h _ {2} \dots h _ {n} $$

as $n$ dummies, it is much cleaner to introduce the single dummy $h$ , of type index $\rightarrow$ index . Note that such a dummy ranges over ${n}^{n}$ different values.

With $p,q$ ranging over the type index

and using the infix dot for function

$\left( {0}^{\prime }\right) \;{A}{i}^{j} = \left\langle {\pi p : \underline{A}}{i.p}^{j \cdot p}\right\rangle$

and the proof of Lemma 0 would have

$$ (A \cdot B) _ {i} ^ {j} $$

$$ \begin{array}{l} = {0 ^ {\prime} } \ \langle \pi_ {p}: (A \cdot B) _ {i, p} ^ {j, p} \rangle \ = {\mathrm {d e f . o f m a t r i x p r o d u c t} } \ \langle \pi_ {p}: (A _ {i, p} ^ {q} B _ {q} ^ {j, p}) \rangle \ = {\mathrm {d i s t r i b u t i o n o f} \pi \mathrm {o v e r} \Sigma } \ \langle \sum k: \langle \pi_ {p}: A _ {i, p} ^ {k, p} B _ {k, p} ^ {j, p} \rangle \rangle \ \end{array} $$

etc.

Note how in the last step the n summations over the index q have been replaced by a single summation over the function $k$ .

With thanks to the ETAC, A. BgIsma in particular. Austin, 2 November 1997

prof. dr Edsger W. Dykstra Department of Computer Sciences The University of Texas at Austin Austin, TX 78712 - 1188, USA