Various Proofs of Sylvester’s (Determinant) Identity

IMACS Symposium SC–1993

Alkiviadis G. Akritas^{∗}, Evgenia K. Akritas, University of Kansas Department of Computer Science Lawrence, KS 66045-2192, USA

Genadii I. Malaschonok Kiev University Department of Cybernetics Vladimirska 64 U-252017 Kiev, Ukraine

February 7, 2002

Abstract: Despite the fact that the importance of Sylvester’s determinant identity has been recognized in the past, we were able to find only one proof of it in English [3], with reference to some others. (Recall that Sylvester stated this theorem without proof [10].) Having used this identity, recently, in the validity proof of our new, improved, matrix-triangularization subresultant polynomial remainder sequence method [1], we decided to collect all the proofs we found of this identity — one in English, four in German and two in Russian, in that order — in a single paper [2]. It turns out that the proof in English is identical to an earlier one in German. Due to space limitations two proofs are omitted.

Keywords: Sylvester’s identity, polynomial remainder sequence (prs), matrix-triangularization subresultant prs

1 Introduction

Throughout this paper we consider an n × n matrix A = (a_{ij}), (i, j = 1, 2, …, n) with elements a_{ij} and determinant |A|, also written det A. We introduce the notation

a_{ij}^{k} = | \begin{matrix}a_{11} & … & a_{1,k−1} & a_{1j} \\ ⋮ & ... & ⋮ & ⋮ \\ a_{k−1,1} & … & a_{k−1,k−1} & a_{k−1,j} \\ a_{i1} & … & a_{i,k−1} & a_{ij} \end{matrix} |

with 1 ≤ k ≤ n, and k ≤ i, j ≤ n; that is, this determinant, of order k, is obtained from the matrix A by adding row i and column j to the upper left corner minor of order k − 1. If we set a_{00}^{0} = 1, then for 1 ≤ p ≤ n, Sylvester’s identity can be expressed as

det D_{p}(A) = (det A) · (a_{p−1,p−1}^{p−1})^{n−p}, (1) where

D_{p}(A) = ( \begin{matrix}a_{pp}^{p} & a_{p,p+1}^{p} & … & a_{pn}^{p} \\ a_{p+1,p}^{p} & a_{p+1,p+1}^{p} & … & a_{p+1,n}^{p} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{np}^{p} & a_{n,p+1}^{p} & … & a_{nn}^{p} \end{matrix} )

of order n − p + 1 and a_{ij}^{p}, (p, i, j = 1, 2, …, n) are minors, of order p, obtained from matrix A by adding row i and column j to the (upper left) corner minor of order p − 1 (see for example [3], [6], [7] and [8, pages 30–35]). Note that

(a_{ij}^{1}) = (a_{ij}), (i, j = 1, 2, …, n),

as well as the fact (easily shown using any of the proofs of the following section) that (1) is valid over an integral domain. To see an application of Sylvester’s identity consider the process of matrix-triangularization over the integers [7]; it is assumed that all diagonal minors of A are different from zero:

a_{kk}^{k} ≠ 0, k = 1, 2, …, n.

∗Partially supported by GRF grant 3089-XX-0038 (1993) of the University of Kansas

In the first step of this process, matrix A(= A^{(1)}) is transformed in the following way: from each row with index i, i ≥ 2, multiplied times a_{11}, subtract the first row multiplied times a_{i1}. The elements of the resulting matrix A^{(2)} are as follows:

a_{1j}^{2} = a_{1j}^{1}, a_{i1}^{2} = 0 and a_{ij}^{2} for i > 1,

where the notation was introduced above. Observe that the elements of A^{(2)} have grown in size and the same is expected of the elements of each subsequently updated matrix. This growth needs to be controlled in order to avoid wasting computer memory and time. Using (1), at the kth step, k ≥ 2, the elements of A^{(k+1)} can be reduced by dividing out a diagonal minor of order k − 1. To see this, assume that at the (k − 1)th step we obtained matrix A^{(k)} with elements

a_{ij}^{k} = \{ \begin{matrix}a_{ij}^{i} & for i = 1, 2, …, k − 1, j ≥ i \\ 0 & for i > j, j = 1, 2, …, k − 1, \\ a_{ij}^{k} & for i, j ≥ k. \end{matrix}

Then, at the kth step matrix A^{(k)} is transformed as follows: from each row with index i, i ≥ k + 1, multiplied times a_{kk}^{k}, subtract the row with index k, multiplied times a_{ik}^{k}; then the (i, j)th element of row i, j ≥ k + 1, is of the form

a_{kk}^{k} · a_{ij}^{k} − a_{ik}^{k} · a_{kj}^{k}, (2)

and in the first k columns there are zeros. Consider now (1) with det A = a_{ij}^{k+1}, of order k + 1, for k < i ≤ n, k < j ≤ n, and under the condition p = k; we then obtain:

| \begin{matrix}a_{kk}^{k} & a_{kj}^{k} \\ a_{ik}^{k} & a_{ij}^{k} \end{matrix} | = a_{ij}^{k+1} · a_{k−1,k−1}^{k−1}

from which we see that (2), and hence all the updated elements of A^{(k+1)}, can be reduced by dividing out the diagonal minor of order k − 1.

2 The various proofs

In this section we present all seven proofs of Sylvester’s identity (1). However, due to space restrictions, only three are presented in full: the one by Bareiss, one proved with the help of Jacobi’s Theorem and one by Malaschonok; a brief outline is given for the rest. The whole presentation is in the alphabetical order of the language they were written in; namely, we first present Bareiss’s proof (written in English), then the four proofs found in Kowalewski’s book (written in German) and finally Malaschonok’s proofs (written in Russian). We will also denote them as B, K1, K2, K3, K4, M1, M2 respectively, and we will try to compare them.

2.1 Bareiss’s proof (B)

This proof of (1), [3], is a compact form of K2, the proof found in Kowalewski’s book [6, pages 91–93], and is based on the fact that

A^{−1} = \frac{1}{|A|} · (adj A), (3)

where the determinant of A is assumed ≠ 0, and (adj A) is the n × n matrix whose (i, j)th entry (adj A)_{ij} is (−1)^{i+j} det A_{ji} = α_{ij}; α_{ji} is the algebraic complement of a_{ij} and A_{ij} is the matrix obtained by crossing out the ith row and the jth column:

(adj A) = (α_{ij})^{t},

the transpose of (α_{ij}), where α_{ij} = (−1)^{i+j} det A_{ij}. The above equation is a direct corollary of the well known fact that

(adj A) · A = |A| · I,

where I is the identity matrix. (See also Sections 2.3 and 2.7.) To start the proof of (1), we partition A and factor by block triangularization such that

A = ( \begin{matrix}W & X \\ Y & Z \end{matrix} ) = ( \begin{matrix}W & 0 \\ Y & I \end{matrix} ) ·

( \begin{matrix}I & W^{−1}X \\ 0 & Z − Y W^{−1}X \end{matrix} ) ,

where W is a nonsingular square matrix of order p−1. Then

|A| = |W | · |Z − Y W^{−1}X| (4)

Multiplying both sides by |W |^{n−p}, equation (4) becomes

|W |^{n−p}|A| = ||W | · |Z − Y W^{−1}X|| (5)

because the second determinant on the right side of (4) is of order (n − p + 1). Consider a_{ij}^{p}, the determinant of order p, (p ≤ i, j ≤ n) which is |W | bordered by a row and a column. If we apply now the identity (4) to each element of the determinant on the right side of (5) we obtain

|W | · (a_{ij} − ∑_{r=1}^{p−1} ∑_{s=1}^{p−1} a_{ir}(W^{−1})_{rs}a_{sj}) =

a_{ij}^{p}, (p ≤ i, j ≤ n). (6)

Since |W | = a_{p−1,p−1}^{p−1}, equation (5) takes the form of Sylvester’s identity (1). □

The validity of equation (6) can be seen if we expand a_{ij}^{p} by minors according to the last column, then expand each minor (except |W |) according to the last row and, finally, make use of (3).

2.2 First proof in Kowalewski’s book (K1)

This proof of (1), due to Studnic̆ka [6, pages 76–80], is based on induction. It is straight forward and rather long, no special theorems are used, and can be understood even by high school students. For details see [2] or [6].

2.3 Second proof in Kowalewski’s book (K2)

This proof of (1) [6, pages 91–93] is the long version of the one presented by Bareiss. Namely, both B and K2 are different versions of one and the same proof, since they are based on the identity

a_{rs}^{p} = a_{rs}a_{p−1,p−1}^{p−1} − ∑_{ρ=1}^{p−1} ∑_{σ=1}^{p−1} a_{ρs}a_{rσ}\overline{a_{ρσ}},

where \overline{a_{ρσ}} denotes the algebraic complement of a_{ρσ} in a_{p−1,p−1}^{p−1}. The only difference between the two proofs is that, in K2, the composition of rows, premultiplied times a coefficient, corresponds to matrix multiplication in B. (See also Sections 2.1 and 2.7.)

2.4 Third proof in Kowalewski’s book (K3)

This is an elegant proof of (1) [6, pages 93–94] based on Jacobi’s identity [5], which can be stated as follows:

Jacobi 1841: Let |A| ≠ 0 be a nonvanishing determinant, and let |(adj A)| be its adjoint determinant. Moreover, let |(adj Ã)^{p}|, of order p, be a minor of |(adj A)|, and let ã_{rs}^{p} be the corresponding minor of |A|. Then |(adj Ã)^{p}| differs from the algebraic complement of ã_{rs}^{p} by the factor |A|^{p−1}.

The third proof of (1) can now be stated as follows: Consider |A| as defined above, and its adjoint determinant |(adj A)|, defined as:

|(adj A)| =

| \begin{matrix}(adj A)_{11} & (adj A)_{12} & … & (adj A)_{1n} \\ (adj A)_{21} & (adj A)_{22} & … & (adj A)_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ (adj A)_{n1} & (adj A)_{n2} & … & (adj A)_{nn} \end{matrix} | (7)

where we follow Kowalewski’s notation now and do not transpose the matrix. In (7) consider the minor

|(adj Ã)^{n−p+1}| =

| \begin{matrix}(adj A)_{pp} & … & (adj A)_{pn} \\ ⋮ & ... & ⋮ \\ (adj A)_{np} & … & (adj A)_{nn} \end{matrix} | . (8)

If we now delete in (8) row r and column s (r, s = p, …, n), we obtain a determinant of order (n − p), which by Jacobi’s Theorem above is equal to:

|A|^{n−p+1} · | \begin{matrix}a_{11} & … & a_{1,p−1} & a_{1s} \\ ⋮ & ... & ⋮ & ⋮ \\ a_{p−1,1} & … & a_{p−1,p−1} & a_{p−1,s} \\ a_{r1} & … & a_{r,p−1} & a_{rs} \end{matrix} | =

|A|^{n−p+1}a_{rs}^{p}

multiplied times (−1)^{r+s}.

However, the algebraic complement of (adj A)_{rs} in |(adj Ã)^{n−p+1}| is also

|A|^{n−p+1}a_{rs}^{p}

and, therefore, the determinant adjoint to |(adj Ã)^{n−p+1}| has the value

|A|^{(n−p+1)(n−p−1)} · | \begin{matrix}a_{pp}^{p} & … & a_{pn}^{p} \\ ⋮ & ... & ⋮ \\ a_{np}^{p} & … & a_{nn}^{p} \end{matrix} | .

On the other hand, since

|(adj A)| = |A|^{n−1}

this adjoint determinant is equal to

|(adj Ã)^{n−p+1}|^{n−p}

or, since (by Jacobi’s Theorem)

|(adj Ã)^{n−p+1}| =

| \begin{matrix}a_{11} & … & a_{1,p−1} \\ ⋮ & ... & ⋮ \\ a_{p−1,1} & … & a_{p−1,p−1} \end{matrix} | · |A|^{n−p}

this adjoint determinant is equal to

|A|^{(n−p)^{2}} · | \begin{matrix}a_{11} & … & a_{1,p−1} \\ ⋮ & ... & ⋮ \\ a_{p−1,1} & … & a_{p−1,p−1} \end{matrix} |^{n−p} .

¿From the above it follows that

| \begin{matrix}a_{pp}^{p} & … & a_{pn}^{p} \\ ⋮ & ... & ⋮ \\ a_{np}^{p} & … & a_{nn}^{p} \end{matrix} | =

|A| · | \begin{matrix}a_{11} & … & a_{1,p−1} \\ ⋮ & ... & ⋮ \\ a_{p−1,1} & … & a_{p−1,p−1} \end{matrix} |^{n−p}

which is Sylvester’s identity. □

2.5 Fourth proof in Kowalewski’s book (K4)

This gives us more than just the proof of Sylvester’s identity (1); namely, it proves [6, pages 100–101] the generalized identity of Sylvester, also known as the Sylvester-Kowalewski identity, a partial instance of which is Sylvester’s identity. The generalized identity can be expressed as :

det D_{m}(A) = (a_{p−1,p−1}^{p−1})^{\binom{n−p}{m−p+1}} · |A|^{\binom{n−p}{m−p}}, (9)

from which we see that, for m = p, (4) reduces to (1).

2.6 Malaschonok’s first proof (M1)

This proof of (1), [7], differs from the other ones in that it does not require matrix A to be defined over a field, and, therefore, does not require a special proof for the case det A = 0, based on the continuity of the determinants. Hence, M1 applies to matrices over any commutative ring. This proof is based on the following equation (which is obtained by expanding a_{ij}^{p} according to the last column) :

a_{ij}^{p} = a_{p−1,p−1}^{p−1}a_{ij} − ∑_{s=1}^{p−1} a_{sj}a_{(si)}^{p−1}, (10)

where 2 ≤ p ≤ n, 1 ≤ i, j ≤ n, a_{(si)}^{p−1} is the minor of order p − 1, which is located in the upper left corner of A, if in A we replace row s, (s ≤ p), by row i, and

a_{ij}^{p} = 0 for 2 ≤ p ≤ n, i < p, j ≤ n

or for 2 ≤ p ≤ n, i ≤ n j < p. (11)

To prove Sylvester’s identity we transform matrix A in the following way: we multiply each row with number i, p ≤ i ≤ n, times a_{p−1,p−1}^{p−1} and subtract from it each one of the rows with numbers s, 1 ≤ s < p, multiplied times the minor a_{(si)}^{p−1}. The resulting matrix is then

T = (t_{ij}), i, j = 1, 2, …, n,

with elements

t_{ij} = \{ \begin{matrix}a_{ij}, \\ 1 ≤ i < p + 1, 1 ≤ j ≤ n, \\ a_{p−1,p−1}^{p−1}a_{ij} − ∑_{s=1}^{p−1} a_{sj}a_{(si)}^{p−1}, \\ p + 1 ≤ i ≤ n, 1 ≤ j ≤ n, \end{matrix}

and determinant

det T = (det A) · (a_{p−1,p−1}^{p−1})^{n−p}. (12)

If we make use of (10) and (11), then it is possible to write the matrix T as follows :

T =

( \begin{matrix}a_{11} & ⋯ & a_{1,p−1} & a_{1p} & ⋯ & a_{1n} \\ a_{21} & ⋯ & a_{2,p−1} & a_{2p} & ⋯ & a_{2n} \\ ⋮ & & ... & & & ⋮ \\ a_{p1} & ⋯ & a_{p,p−1} & a_{pp} & ⋯ & a_{pn} \\ 0 & ⋯ & 0 & a_{p+1,p}^{p} & ⋯ & a_{p+1,n}^{p} \\ ⋮ & & ⋮ & & & ⋮ \\ 0 & ⋯ & 0 & a_{np}^{p} & ⋯ & a_{nn}^{p} \end{matrix} ) .

If we expand the above matrix T according to the minors contained in the first p rows, using Laplace’s theorem

|A| = ∑ |M||\overline{M}|,

where \overline{M} is the algebraic complement of M, and the sum is taken over the \binom{n}{m} products (m being the specified rows containing the minors), we have :

det T = ∑_{s=p}^{n}(−1)^{p+s}|T [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] |·

|\overline{T} [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] |, (13)

where in the brackets above, the first row indicates which rows of T are used and the second row indicates which columns of T are used. Here we consider that all minors of the type

|\overline{T} [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] |,

which are obtained by crossing out rows 1, 2, …, p and columns q_{1}, q_{2}, …, q_{p}, are equal to zero, except for those minors in which among the crossed out columns q_{1}, q_{2}, …, q_{p}, are contained all the zero columns 1, 2, …, p − 1. Comparing the matrices A, D_{p}(A) and T, we observe that there exist the following two equalities of minors for s ≥ p :

|T [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] | =

|A [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] | = a_{ps}^{p},

|\overline{T} [ \begin{matrix}1, 2, …, p \\ 1, 2, …, p − 1, s \end{matrix} ] | = |\overline{D_{p}(A)} [ \begin{matrix}p \\ s \end{matrix} ] |

Therefore, equation (13) now becomes

det T = ∑_{s=p}^{n}(−1)^{1+(s−p+1)}a_{ps}^{p}|\overline{D_{p}(A)} [ \begin{matrix}p \\ s \end{matrix} ] |.

However, the right-hand side of the above equation represents the expansion of the determinant of the matrix D_{p}(A) by the first row. Therefore, we arrive at the equality :

det D_{p}(A) = det T. (14)

Finally, from equations (12) and (14) immediately follows Sylvester’s identity (1). □

2.7 Malaschonok’s second proof (M2)

This proof is based on (10) and (11) of the previous section. To begin the proof, let

A = ( \begin{matrix}W & X \\ Y & Z \end{matrix} )

where W is a square submatrix of order p − 1; more precisely, we have det W = a_{p−1,p−1}^{p−1}. Moreover, let

I_{p−1} = ( \begin{matrix}1 & & & & 0 \\ & . & . & . \\ 0 & & & & 1 \end{matrix} )

be the identity diagonal matrix of order p−1, and let

I_{n−p+1}(a) = ( \begin{matrix}a_{p−1,p−1}^{p−1} & & & & 0 \\ & . & . & . \\ 0 & & & & a_{p−1,p−1}^{p−1} \end{matrix} )

be the diagonal matrix of order n−p+1, with elements a_{p−1,p−1}^{p−1}. Set

[i, j] = det W_{(ij)}

where W_{(ij)} is obtained from W by replacing row i by row j (i.e. using the convention established in the previous section we have [i, j] = a_{(ij)}^{p−1}) and consider the (n − p + 1) × (p − 1) matrix

A′ = ( \begin{matrix}[1, p] & … & [p − 1, p] \\ ⋮ & ... & ⋮ \\ [1, n] & … & [p − 1, n] \end{matrix} ) .

Then, using (10) and (11), we have the matrix identity:

( \begin{matrix}I_{p−1} & 0 \\ A′ & I_{n−p+1}(a) \end{matrix} ) A = ( \begin{matrix}W & X \\ 0 & D_{p}(A) \end{matrix} )(15)

from which we obtain the determinantal identity

(a_{p−1,p−1}^{p−1})^{n−p+1} · (det A) =

(det D_{p}(A)) · a_{p−1,p−1}^{p−1}

and after cancellations Sylvester’s identity (1). □

Comparing M2 with B, or K2, we see that B (and K2) are based on the inverse matrix transformation of (15); namely, they are based on

A = ( \begin{matrix}I_{p−1} & 0 \\ A′ & I_{n−p+1}(a) \end{matrix} )^{−1} ( \begin{matrix}W & X \\ 0 & D_{p}(A) \end{matrix} ) .

3 Conclusion

We are, thus, done with the presentation of the proofs of Sylvester’s determinant identity (1). It is rather unfortunate that, due to “its inclusion as merely one of a class of theorems” [9, page 60], none of the proofs of this identity can be found in the English-language books on matrix theory [4]. Despite all these, using Sylvester’s identity we were able to obtain elegant proofs for the validity of the new, improved, matrix-triangularization subresultant prs method [1]. Therefore, there can be no doubt that, (not only) at the time of its discovery, this identity was — as Sylvester himself styled it — “a remarkable theorem” [9, page 60].

References

[1] Akritas, A.G., E.K. Akritas and G.I. Malaschonok. Computation of polynomial remainder sequences in integral domains. Submitted for publication.

[2] Akritas, A.G., E.K. Akritas and G.I. Malaschonok. Various proofs of Sylvester’s (determinant) identity. Technical Report, University of Kansas.

[3] Bareiss, E.H. Sylvester’s identity and multistep integer preserving Gaussian elimination. Mathematics of Computation 22, 565–578, 1968.

[4] Horn, R.A. and C.A. Johnson. Topics in matrix analysis. Cambridge University Press, New York, 1991.

[5] Jacobi, C.G.J. Ueber die Bildung und die Eigenschaften der Determinanten (De formatione et proprietatibus Determinantum 1841). Edited by Stäkel.

[6] Kowalewski, G. Einfürung in die Determinantentheorie. Chelsea, New York, 1948.

[7] Malaschonok, G.I. Solution of a system of linear equations in an integral domain. USSR Journal of Computational Mathematics and Mathematical Physics 23, 1497–1500, 1983 (in Russian).

[8] Malaschonok, G.I. System of linear equations over a commutative ring. Academy of Sciences of Ukraine. Lvov, 1986 (in Russian).

[9] Muir, T. The theory of Determinants. Dover, New York.

[10] Sylvester, J.J. On the relation between the minor determinants of linearly equivalent quadratic functions. Philosophical Magazine 1, (Fourth Series), 295–305, 1851.