 # Dr. Mark V. Sapir

## Determinants

You already know the definition of the determinant of a 2 by 2 matrix

 [ a b ] [ c d ]

The determinant of this matrix is ad-bc. You also know how to calculate the determinant of a 3 by 3 matrix (remember the cross product!). Before we define the determinant of an arbitrary n by n matrix, consider an example. Let Maple find the determinant of the following 4 by 4 matrix:

 A := [ a11 a12 a13 a14 ] [ a21 a22 a23 a24 ] [ a31 a32 a33 a34 ] [ a41 a42 a43 a44 ]
The result of Maple's calculations can be written in the following form:
```det(A) = a11 a22 a33 a44 - a11 a22 a43 a34 - a11 a32 a23 a44 + a11 a32 a43 a24

+ a11 a42 a23 a34 - a11 a42 a33 a24 - a21 a12 a33 a44 + a21 a12 a43 a34

+ a21 a32 a13 a44 - a21 a32 a43 a14 - a21 a42 a13 a34 + a21 a42 a33 a14

+ a31 a12 a23 a44 - a31 a12 a43 a24 - a31 a22 a13 a44 + a31 a22 a43 a14

+ a31 a42 a13 a24 - a31 a42 a23 a14 - a41 a12 a23 a34 + a41 a12 a33 a24

+ a41 a22 a13 a34 - a41 a22 a33 a14 - a41 a32 a13 a24 + a41 a32 a23 a14
```

One can notice the following features of this expression:

1. The sum contains 24 terms (6 rows, 4 terms in a row).
2. Each term is a product of 4 entries of the matrix A.
3. The second indexes of these entries in each of the terms form the sequence (1,2,3,4).
4. The first indexes form a permutation of the set {1,2,3,4}.
5. All terms are different (otherwise we would combine them), so all the permutations must be different. Since there are exactly 24 permutations of 4 numbers, every permutation corresponds to one of the terms in the sum. Thus we have a one-to-one correspondence between permutations of the set {1,2,3,4} and the terms in det(A).
6. Suppose that one of the permutations is obtained from another one by one transposition, that is one switching of two numbers, (like the permulations (1,3,4,2) and (1,2,4,3)) then the corresponding terms have opposite signs. Indeed, for example the term
a11 a32 a43 a24

has the positive sign and the term

a11 a22 a43 a34

has the negative sign.

The last observation leads us to a discovery of the rule according to which Maple chooses the signs in the expression for det(A). Indeed, since the term corresponding to the "trivial" permutation (1,2,3,4),

a11 a22 a33 a44

has positive sign, we can say that the sign of a term is positive if the permutation corresponding to this term is obtained from the trivial permutation by an even number of transpositions, otherwise the sign is negative.

Thus we can give the following definition of the determinant of a square matrix A. Let A be a square n by n matrix. List all permutations p=(p1,...,pn) of numbers {1,...,n} -- there are n factorial of them. For each permutation p consider the product

(-1)p A(p1,1) A(p2,2)... A(pn,n)

of entries of matrix A. Here (-1)p denotes the sign of the permutation p that is "+" if p can be obtained from the trivial permutation by an even number of transpositions and "-" otherwise. Then the determinant det(A) is equal to the sum of all these (n factorial) products.

The sign of a permutation can be calculated in a different way. We say that a permutation p=(p1,...,pn) of numbers {1,...,n} has an inversion if a larger number precedes a smaller number in this permutation. For example, permutation (4,3,2,1) has 6 inversions: 4 precedes 3, 2 and 1 (three inversions), 3 precedes 2 and 1 (two inversions), 2 precedes 1 (one inversion).

Theorem. The sign of a permutation is "+" if and only if the number of inversions in this permutation is even.

To see a hint to a prove of this theorem, click here.

Thus we have two equivalent definitions of the sign of a permutation. We call a permutation even if its sign is "+", otherwise the permutation is called odd.

## Properties of determinants

Here we establish several important properties of determinants. We start with some simple properties and then deduce more and more complex ones. Each step will be relatively simple but at the end we shall get some very non-trivial statements. Theorem. Let A be an n by n matrix. Then the following conditions hold.

1. If we multiply a row (column) of A by a number, the determinant of A will be multiplied by the same number.
2. If the i-th row (column) in A is a sum of the i-th row (column) of a matrix B and the i-th row (column) of a matrix C and all other rows in B and C are equal to the corresponding rows in A (that is B and C differ from A by one row only), then det(A)=det(B)+det(C).
3. If two rows (columns) in A are equal then det(A)=0.
4. If we add a row (column) of A multiplied by a scalar k to another row (column) of A, then the determinant will not change.
5. If we swap two rows (columns) in A, the determinant will change its sign.
6. det(A)=det(AT).  Theorem. Let A be an n by n matrix. Then the following conditions hold.

1. If A has a zero row (column) then det(A)=0.
2. If the last row (column) of A contains exactly one non-zero number A(n,n) then

det(A)=A(n,n)*Cnn

where Cnn is the cofactor of entry A(n,n) that is the determinant of the matrix obtained by deleting the last row and the last column of matrix A.

3. If the i-th row (column) of A contains exactly one non-zero entry A(i,j) (i, j are between 1 and n) then
det(A)=A(i,j)*Cij
where Cij is the cofactor of entry A(i,j) that is (-1)i+j multiplied by the determinant of the matrix obtained from A by deleting the i-th row and the j-th column (the determinant of this smaller matrix has a special name also; it is called the minor of entry A(i,j)).
4. For every i=1,...,n we have
det(A)=A(i,1) Ci1 + A(i,2) Ci2 +...+ A(i,n) Cin
This is called the cofactor expansion of det(A) along the i-th row (a similar statement holds for columns).
5. The determinant of a triangular matrix is the product of the diagonal entries.  Theorem. Let A and B be n by n matrices. Then the following conditions hold.

a) If A is an elementary matrix then det(AB)=det(A)det(B).

b) A is invertible if and only if det(A) is not 0.

c) det(AB)=det(A)det(B) (the matrix A is arbitrary here). Example  ## Corollaries

Corollary 1. If A and B are square matrices and AB=I then A is invertible (recall that in the definition of invertible matrices we also required that BA=I; this corollary shows that this requirement is not necessary).

Proof. Indeed, if AB=I the by the third theorem about determinants

det(A)*det(B)=det(AB)=det(I)=1

Therefore det(A) is not zero (otherwise 0=1). Again by the third theorem about determinants this implies that A is invertible.

Corollary 2.If A is an n by n matrix and i and j are different numbers from 1 to n then

A(i,1)Cj1+A(i,2)Cj2+...+A(i,n)Cjn=0
(notice that in this sum the entries A(i,k) are taken from the i-th row and the cofactors correspond to entries of the j-th row; recall also that by the second theorem about determinants if i=j then this sum is equal to det(A)).

Proof. Indeed, let us replace the i-th row of A by the j-th row of A and call the resulting matrix B. Then the sum in the left hand side of our equality is the cofactor expansion of the matrix B along the j-th row. Thus by the second theorem about determinants this sum is equal to det(B). But B has two equal rows (row i and row j) thus det(B)=0, so the equality holds.

Definition. If A is any n by n matrix and Cij is the cofactor of A(i,j) then the matrix

 [ C11 C21 ... Cn1 ] [ C12 C22 ... Cn2 ] ............................ [ C1n C2n ... Cnn ]
is called the adjoint of A, denoted adj(A). (Notice that this matrix is obtained by replacing each entry of A by its cofactor and then taking the transpose.)

Corollary 3. If A is an n by n matrix then

A*adj(A) = det(A)*I =adj(A)*A

Proof. We shall prove only the first equality because the second one is similar. Let B=A*adj(A). Then B(i,j) is the product of the i-th row of A by the j-th column of adj(A). But if we multiply this row and this column, we get the sum from the previous corollary. As we noticed before, if i equals j then this sum is the cofactor expansion of A along the i-th row, so it is equal to det(A). If i is not equal to j then the sum is 0. Thus

B(i,i)=det(A), B(i,j)=0 (i and j are different numbers from 1 to n).

Therefore B=det(A)*i.

Corollary 4. If A is invertible then

A-1 = (1/det(A)) adj(A)

Proof. Indeed, if A is invertible then by the third theorem about determinants det(A) is not zero. Therefore we can multiply the equality from the previous corollary by 1/det(A) and get

A*(1/det(A))adj(A)=I,
Multiplying this equality by A-1 on the left we get:
(1/det(A))adj(A)=A-1 .

## Cramer's rule

Using the adjoint matrix, we can formulate a new algorithm for solving systems of linear equations with invertible matrix of coefficients. Let
A v = b
be such a system (A is invertible), v is the column vector of unknowns, b is the column vector of the right sides. Multiply both sides by adj(A) on the left:
(adj(A)*A)) v= adj(A)*b
Using the third corollary from the theorems about determinants we get: det(A)*I*v=adj(A)*b Since I*v=v, we have:
det(A)*v=adj(A)*b
Thus
```			           [ det(A)*x1  ]  [ b1C11+b2C21+...+bnCn1 ]
[ det(A)*x2  ]  [ b1C12+b2C22+...+bnCn2 ]
.......    =     ................
[ det(A)*xn  ]  [ b1C1n+b2C2n+...+bnCnn ]
```
From this, we can deduce that for every i=1,2,...,n

det(A)*xi = b1C1i+ b2C2i + ... + bnCni
The right hand side of this equality is the cofactor expansion along the i-th column of the matrix, say, Ai obtained from A by replacing the entries of the i-th column by the entries of b. Therefore this right hand side is equal to det(Ai). Thus we can formulate the rule:

(Cramer's rule) If A is an invertible matrix then the solution of the system of linear equalitions

A*v=b

can be written as

x1=det(A1)/det(A),
...,
xn=det(An)/det(A)

where Ai is the matrix obtained from A by replacing the i-th column by the column vector b.

Notice that Cramer's rule is much less efficient for large systems of equations than the Gauss-Jordan algorithm. But it is more useful is research applications when we want to find out general properties of systems of linear equations. Notice also that a form of Cramer's rule can be used even if det(A)=0, that is when A is not invertible. We shall return to it later.

Example   