Linear Algebra, The Permutation Expansion

The prior subsection defines a function to be a determinant if it
satisfies four conditions and
shows that there is at most one n \ × \ n determinant function for
each n.
What is left is to show that for each n such a function exists.

How could such a function not exist?
After all, we have done computations that start with a square matrix,
follow the conditions, and end with a number.

The difficulty is that, as far as we know,
the computation might not give a well-defined result.
To illustrate this possibility,
suppose that we were to change the second condition in the definition of
determinant to be that the value of a determinant does not change on
a row swap.
By Remark 2.2 we know that this conflicts with the
first and third conditions.
Here is an instance of the conflict: here are
two Gauss' method reductions of the same matrix, the first without any row swap

( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} ) {→}_{ \ }^{− 3 {ρ}_{1} + {ρ}_{2}} ( \begin{matrix}1 & 2 \\ 0 & − 2\end{matrix} )

and the second with a swap.

( \begin{matrix}1 & 2 \\ 3 & 4\end{matrix} ) {→}_{ \ }^{{ρ}_{1} ↔ {ρ}_{2}} ( \begin{matrix}3 & 4 \\ 1 & 2\end{matrix} ) {→}_{ \ }^{− ( 1 / 3 ) {ρ}_{1} + {ρ}_{2}} ( \begin{matrix}3 & 4 \\ 0 & 2 / 3\end{matrix} )

Following Definition 2.1 gives that both
calculations yield the determinant − 2
since in the second one
we keep track of the fact that the row swap changes the sign of the result
of multiplying down the diagonal.
But if we follow the supposition and
change the second condition then the two calculations yield
different values, − 2 and 2.
That is, under the supposition the outcome would not be well-defined — no
function exists that satisfies the changed second condition
along with the other three.

Of course, observing that Definition 2.1 does the right thing
in this one instance is not enough; what we will do in the rest of this
section is to show that there is never a conflict.
The natural way to try this would be
to define the determinant function with: "The value of the
function is the result of doing Gauss' method,
keeping track of row swaps, and finishing by multiplying down the diagonal".
(Since Gauss' method allows for some variation, such as a
choice of which row to use when swapping,
we would have to fix an explicit algorithm.)
Then we would be done if we verified that
this way of computing the determinant satisfies the four properties.
For instance, if T and \overset{̂}{T}
are related by a row swap then we would need to show that this
algorithm returns determinants that are negatives of each other.
However, how to verify this is not evident.
So the development below will not proceed in this way.
Instead, in this subsection we will define a different way to compute
the value of a determinant, a formula, and we will use this way to
prove that the conditions are satisfied.

The formula that we shall use is based on an insight gotten from
property (3) of the definition of determinants.
This property shows that determinants are not linear.

Example 3.1

For this matrix
det ⁡ ( 2 A ) ≠ 2 ⋅ det ⁡ ( A ).

A = ( \begin{matrix}2 & 1 \\ − 1 & 3\end{matrix} )

Instead, the scalar comes out of each of the two rows.

| \begin{matrix}4 & 2 \\ − 2 & 6\end{matrix} | = 2 ⋅ | \begin{matrix}2 & 1 \\ − 2 & 6\end{matrix} | = 4 ⋅ | \begin{matrix}2 & 1 \\ − 1 & 3\end{matrix} |

Since scalars come out a row at a time, we might guess that
determinants are linear a row at a time.

Definition 3.2

Let V be a vector space.
A map f : {V}^{n} → ℝ is
multilinear
if

f ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} + \overset{→}{w} , … , {\overset{→}{ρ}}_{n} ) = f ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} , … , {\overset{→}{ρ}}_{n} ) + f ( {\overset{→}{ρ}}_{1} , … , \overset{→}{w} , … , {\overset{→}{ρ}}_{n} )

f ( {\overset{→}{ρ}}_{1} , … , k \overset{→}{v} , … , {\overset{→}{ρ}}_{n} ) = k ⋅ f ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} , … , {\overset{→}{ρ}}_{n} )

for \overset{→}{v} , \overset{→}{w} ∈ V and k ∈ ℝ.

Lemma 3.3

Determinants are multilinear.

Proof

The definition of determinants gives property (2)
(Lemma 2.3 following that definition
covers the k = 0 case) so we need only check property (1).

det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} + \overset{→}{w} , … , {\overset{→}{ρ}}_{n} ) = det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} , … , {\overset{→}{ρ}}_{n} ) + det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{w} , … , {\overset{→}{ρ}}_{n} )

If the set
\{ {\overset{→}{ρ}}_{1} , … , {\overset{→}{ρ}}_{i − 1} , {\overset{→}{ρ}}_{i + 1} , … , {\overset{→}{ρ}}_{n} \}
is linearly dependent then all three matrices are singular and so all
three determinants are zero and the equality is trivial.
Therefore assume that the set is linearly independent.
This set of n-wide row vectors has n − 1 members, so we can make a basis by
adding one more vector
⟨ {\overset{→}{ρ}}_{1} , … , {\overset{→}{ρ}}_{i − 1} , \overset{→}{β} , {\overset{→}{ρ}}_{i + 1} , … , {\overset{→}{ρ}}_{n} ⟩.
Express \overset{→}{v} and \overset{→}{w} with respect to this basis

\begin{matrix}\overset{→}{v} & = {v}_{1} {\overset{→}{ρ}}_{1} + … + {v}_{i − 1} {\overset{→}{ρ}}_{i − 1} + {v}_{i} \overset{→}{β} + {v}_{i + 1} {\overset{→}{ρ}}_{i + 1} + … + {v}_{n} {\overset{→}{ρ}}_{n} \\ \overset{→}{w} & = {w}_{1} {\overset{→}{ρ}}_{1} + … + {w}_{i − 1} {\overset{→}{ρ}}_{i − 1} + {w}_{i} \overset{→}{β} + {w}_{i + 1} {\overset{→}{ρ}}_{i + 1} + … + {w}_{n} {\overset{→}{ρ}}_{n}\end{matrix}

giving this.

\overset{→}{v} + \overset{→}{w} = ( {v}_{1} + {w}_{1} ) {\overset{→}{ρ}}_{1} + … + ( {v}_{i} + {w}_{i} ) \overset{→}{β} + … + ( {v}_{n} + {w}_{n} ) {\overset{→}{ρ}}_{n}

By the definition of determinant, the value of
det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} + \overset{→}{w} , … , {\overset{→}{ρ}}_{n} )
is unchanged by the pivot operation of
adding − ( {v}_{1} + {w}_{1} ) {\overset{→}{ρ}}_{1} to \overset{→}{v} + \overset{→}{w}.

\overset{→}{v} + \overset{→}{w} − ( {v}_{1} + {w}_{1} ) {\overset{→}{ρ}}_{1} = ( {v}_{2} + {w}_{2} ) {\overset{→}{ρ}}_{2} + ⋯ + ( {v}_{i} + {w}_{i} ) \overset{→}{β} + … + ( {v}_{n} + {w}_{n} ) {\overset{→}{ρ}}_{n}

Then, to the result, we can add − ( {v}_{2} + {w}_{2} ) {\overset{→}{ρ}}_{2}, etc.
Thus

det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{v} + \overset{→}{w} , … , {\overset{→}{ρ}}_{n} )

\begin{matrix} & = det ⁡ ( {\overset{→}{ρ}}_{1} , … , ( {v}_{i} + {w}_{i} ) ⋅ \overset{→}{β} , … , {\overset{→}{ρ}}_{n} ) \\ & = ( {v}_{i} + {w}_{i} ) ⋅ det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{β} , … , {\overset{→}{ρ}}_{n} ) \\ & = {v}_{i} ⋅ det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{β} , … , {\overset{→}{ρ}}_{n} ) + {w}_{i} ⋅ det ⁡ ( {\overset{→}{ρ}}_{1} , … , \overset{→}{β} , … , {\overset{→}{ρ}}_{n} )\end{matrix}

(using (2) for the second equality). To finish, bring {v}_{i} and {w}_{i} back inside in front of \overset{→}{β} and use pivoting again, this time to reconstruct the expressions of \overset{→}{v} and \overset{→}{w} in terms of the basis, e.g., start with the pivot operations of adding {v}_{1} {\overset{→}{ρ}}_{1} to {v}_{i} \overset{→}{β} and {w}_{1} {\overset{→}{ρ}}_{1} to {w}_{i} {\overset{→}{ρ}}_{1}, etc.

Multilinearity allows us to expand a determinant into a sum of
determinants, each of which involves a simple matrix.

Example 3.4

We can use multilinearity to split this determinant into two,
first breaking up the first row

| \begin{matrix}2 & 1 \\ 4 & 3\end{matrix} | = | \begin{matrix}2 & 0 \\ 4 & 3\end{matrix} | + | \begin{matrix}0 & 1 \\ 4 & 3\end{matrix} |

and then separating each of those two, breaking along the second rows.

= | \begin{matrix}2 & 0 \\ 4 & 0\end{matrix} | + | \begin{matrix}2 & 0 \\ 0 & 3\end{matrix} | + | \begin{matrix}0 & 1 \\ 4 & 0\end{matrix} | + | \begin{matrix}0 & 1 \\ 0 & 3\end{matrix} |

We are left with four determinants, such that in each row of each matrix there is a single entry from the original matrix.

Example 3.5

In the same way,
a {}3 \ × \ 3 determinant separates into a sum of
many simpler determinants.
We start by splitting along the first row, producing three determinants
(the zero in the {}1 , 3 position is underlined to set it off visually
from the zeroes that appear in the splitting).

| \begin{matrix}2 & 1 & − 1 \\ 4 & 3 & {0}_{_} \\ 2 & 1 & 5\end{matrix} | = | \begin{matrix}2 & 0 & 0 \\ 4 & 3 & {0}_{_} \\ 2 & 1 & 5\end{matrix} | + | \begin{matrix}0 & 1 & 0 \\ 4 & 3 & {0}_{_} \\ 2 & 1 & 5\end{matrix} | + | \begin{matrix}0 & 0 & − 1 \\ 4 & 3 & {0}_{_} \\ 2 & 1 & 5\end{matrix} |

Each of these three will itself split in three along the second row.
Each of the resulting nine splits in three along the third row, resulting
in twenty seven determinants

= | \begin{matrix}2 & 0 & 0 \\ 4 & 0 & 0 \\ 2 & 0 & 0\end{matrix} | + | \begin{matrix}2 & 0 & 0 \\ 4 & 0 & 0 \\ 0 & 1 & 0\end{matrix} | + | \begin{matrix}2 & 0 & 0 \\ 4 & 0 & 0 \\ 0 & 0 & 5\end{matrix} | + | \begin{matrix}2 & 0 & 0 \\ 0 & 3 & 0 \\ 2 & 0 & 0\end{matrix} | + … + | \begin{matrix}0 & 0 & − 1 \\ 0 & 0 & {0}_{_} \\ 0 & 0 & 5\end{matrix} |

such that each row contains a single entry from the starting matrix.

So an n \ × \ n determinant expands into a
sum of {n}^{n} determinants where
each row of each summands contains a single entry from the
starting matrix.
However, many of these summand determinants are zero.

Example 3.6

In each of these three matrices from the above expansion,
two of the rows have their entry from the starting matrix in the same column,
e.g.,
in the first matrix, the 2 and the 4 both come from the first column.

| \begin{matrix}2 & 0 & 0 \\ 4 & 0 & 0 \\ 0 & 1 & 0\end{matrix} | \ | \begin{matrix}0 & 0 & − 1 \\ 0 & 3 & 0 \\ 0 & 0 & 5\end{matrix} | \ | \begin{matrix}0 & 1 & 0 \\ 0 & 0 & {0}_{_} \\ 0 & 0 & 5\end{matrix} |

Any such matrix is singular, because in each,
one row is a multiple of the other (or is a zero row).
Thus, any such determinant is zero, by Lemma 2.3.

Therefore, the above expansion of the {}3 \ × \ 3 determinant into
the sum of the twenty seven determinants simplifies to the sum of these six.

\begin{matrix}| \begin{matrix}2 & 1 & − 1 \\ 4 & 3 & {0}_{_} \\ 2 & 1 & 5\end{matrix} | & = | \begin{matrix}2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 5\end{matrix} | + | \begin{matrix}2 & 0 & 0 \\ 0 & 0 & {0}_{_} \\ 0 & 1 & 0\end{matrix} | \\ & \ + | \begin{matrix}0 & 1 & 0 \\ 4 & 0 & 0 \\ 0 & 0 & 5\end{matrix} | + | \begin{matrix}0 & 1 & 0 \\ 0 & 0 & {0}_{_} \\ 2 & 0 & 0\end{matrix} | \\ & \ + | \begin{matrix}0 & 0 & − 1 \\ 4 & 0 & 0 \\ 0 & 1 & 0\end{matrix} | + | \begin{matrix}0 & 0 & − 1 \\ 0 & 3 & 0 \\ 2 & 0 & 0\end{matrix} |\end{matrix}

We can bring out the scalars.

\begin{matrix} & = ( 2 ) ( 3 ) ( 5 ) | \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{matrix} | + ( 2 ) ( {0}_{_} ) ( 1 ) | \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{matrix} | \\ & \ + ( 1 ) ( 4 ) ( 5 ) | \begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{matrix} | + ( 1 ) ( {0}_{_} ) ( 2 ) | \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{matrix} | \\ & \ + ( − 1 ) ( 4 ) ( 1 ) | \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{matrix} | + ( − 1 ) ( 3 ) ( 2 ) | \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\end{matrix} |\end{matrix}

To finish, we evaluate those six determinants by row-swapping them
to the identity matrix,
keeping track of the resulting sign changes.

\begin{matrix} & = 30 ⋅ ( + 1 ) + 0 ⋅ ( − 1 ) \\ & \ + 20 ⋅ ( − 1 ) + 0 ⋅ ( + 1 ) \\ & \ − 4 ⋅ ( + 1 ) − 6 ⋅ ( − 1 ) = 12\end{matrix}

That example illustrates the key idea.
We've applied multilinearity to a {}3 \ × \ 3 determinant to get
{3}^{3} separate determinants, each with one distinguished entry per row.
We can drop most of these new determinants because the matrices are singular,
with one row a multiple of another.
We are left with the one-entry-per-row determinants
also having only one entry per column (one entry from the original determinant,
that is).
And, since we can factor scalars out, we can further reduce to
only considering determinants of
one-entry-per-row-and-column matrices where the entries are ones.

These are permutation matrices.
Thus, the determinant can be computed in this
three-step way
(Step 1) for each permutation matrix, multiply together
the entries from the original matrix
where that permutation matrix has ones,
(Step 2) multiply that by the determinant of the permutation matrix
and
(Step 3) do that for all permutation matrices
and sum the results together.

To state this as a formula, we introduce a notation for permutation matrices.
Let {ι}_{j} be the row vector that is all zeroes except for a one in its
j-th entry, so that the four-wide {ι}_{2} is ( \begin{matrix}0 & 1 & 0 & 0\end{matrix} ).
We can construct permutation matrices by
permuting — that is, scrambling — the numbers 1, 2, ..., n,
and using them as indices on the ι's.
For instance, to get a {}4 \ × \ 4 permutation matrix
matrix, we can scramble the numbers from 1 to 4 into
this sequence ⟨ 3 , 2 , 1 , 4 ⟩ and take the corresponding
row vector ι's.

( \begin{matrix}{ι}_{3} \\ {ι}_{2} \\ {ι}_{1} \\ {ι}_{4}\end{matrix} ) = ( \begin{matrix}0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1\end{matrix} )

Definition 3.7

An n-permutation is a sequence consisting of an arrangement of the numbers 1, 2, ..., n.

Example 3.8

The 2-permutations are
{ϕ}_{1} = ⟨ 1 , 2 ⟩ and {ϕ}_{2} = ⟨ 2 , 1 ⟩.
These are the associated permutation matrices.

{P}_{{ϕ}_{1}} = ( \begin{matrix}{ι}_{1} \\ {ι}_{2}\end{matrix} ) = ( \begin{matrix}1 & 0 \\ 0 & 1\end{matrix} ) \ {P}_{{ϕ}_{2}} = ( \begin{matrix}{ι}_{2} \\ {ι}_{1}\end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0\end{matrix} )

We sometimes write permutations as functions, e.g., {ϕ}_{2} ( 1 ) = 2,
and {ϕ}_{2} ( 2 ) = 1.
Then the rows of {P}_{{ϕ}_{2}} are
{ι}_{{ϕ}_{2} ( 1 )} = {ι}_{2} and {ι}_{{ϕ}_{2} ( 2 )} = {ι}_{1}.

The 3-permutations are
{ϕ}_{1} = ⟨ 1 , 2 , 3 ⟩,
{ϕ}_{2} = ⟨ 1 , 3 , 2 ⟩,
{ϕ}_{3} = ⟨ 2 , 1 , 3 ⟩,
{ϕ}_{4} = ⟨ 2 , 3 , 1 ⟩,
{ϕ}_{5} = ⟨ 3 , 1 , 2 ⟩, and
{ϕ}_{6} = ⟨ 3 , 2 , 1 ⟩.
Here are two of the associated permutation matrices.

{P}_{{ϕ}_{2}} = ( \begin{matrix}{ι}_{1} \\ {ι}_{3} \\ {ι}_{2}\end{matrix} ) = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{matrix} ) \ {P}_{{ϕ}_{5}} = ( \begin{matrix}{ι}_{3} \\ {ι}_{1} \\ {ι}_{2}\end{matrix} ) = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{matrix} )

For instance, the rows of {P}_{{ϕ}_{5}} are {ι}_{{ϕ}_{5} ( 1 )} = {ι}_{3}, {ι}_{{ϕ}_{5} ( 2 )} = {ι}_{1}, and {ι}_{{ϕ}_{5} ( 3 )} = {ι}_{2}.

Definition 3.9

The permutation expansion for determinants is

| \begin{matrix}{t}_{1 , 1} & {t}_{1 , 2} & … & {t}_{1 , n} \\ {t}_{2 , 1} & {t}_{2 , 2} & … & {t}_{2 , n} \\ & ⋮ \\ {t}_{n , 1} & {t}_{n , 2} & … & {t}_{n , n}\end{matrix} | = \begin{matrix}{t}_{1 , {ϕ}_{1} ( 1 )} {t}_{2 , {ϕ}_{1} ( 2 )} ⋯ {t}_{n , {ϕ}_{1} ( n )} | {P}_{{ϕ}_{1}} | \\ \ + {t}_{1 , {ϕ}_{2} ( 1 )} {t}_{2 , {ϕ}_{2} ( 2 )} ⋯ {t}_{n , {ϕ}_{2} ( n )} | {P}_{{ϕ}_{2}} | \\ \ ⋮ \\ \ + {t}_{1 , {ϕ}_{k} ( 1 )} {t}_{2 , {ϕ}_{k} ( 2 )} ⋯ {t}_{n , {ϕ}_{k} ( n )} | {P}_{{ϕ}_{k}} |\end{matrix}

where {ϕ}_{1} , … , {ϕ}_{k} are all of the n-permutations.

This formula is often written in summation notation

| T | = {∑}_{\text{permutations } ϕ} \ \ \ \ {t}_{1 , ϕ ( 1 )} {t}_{2 , ϕ ( 2 )} ⋯ {t}_{n , ϕ ( n )} | {P}_{ϕ} |

read aloud as
"the sum, over all permutations ϕ, of terms having the form
{t}_{1 , ϕ ( 1 )} {t}_{2 , ϕ ( 2 )} ⋯ {t}_{n , ϕ ( n )} | {P}_{ϕ} |".
This phrase is just a restating of the three-step process
(Step 1) for each permutation matrix, compute
{t}_{1 , ϕ ( 1 )} {t}_{2 , ϕ ( 2 )} ⋯ {t}_{n , ϕ ( n )}
(Step 2) multiply that by | {P}_{ϕ} |
and (Step 3) sum all such terms together.

Example 3.10

The familiar formula for the determinant of a {}2 \ × \ 2 matrix
can be derived in this way.

\begin{matrix}| \begin{matrix}{t}_{1 , 1} & {t}_{1 , 2} \\ {t}_{2 , 1} & {t}_{2 , 2}\end{matrix} | & = {t}_{1 , 1} {t}_{2 , 2} ⋅ | {P}_{{ϕ}_{1}} | + {t}_{1 , 2} {t}_{2 , 1} ⋅ | {P}_{{ϕ}_{2}} | \\ & = {t}_{1 , 1} {t}_{2 , 2} ⋅ | \begin{matrix}1 & 0 \\ 0 & 1\end{matrix} | + {t}_{1 , 2} {t}_{2 , 1} ⋅ | \begin{matrix}0 & 1 \\ 1 & 0\end{matrix} | \\ & = {t}_{1 , 1} {t}_{2 , 2} − {t}_{1 , 2} {t}_{2 , 1}\end{matrix}

(the second permutation matrix takes one row swap to pass to the
identity).
Similarly, the formula for the determinant of a {}3 \ × \ 3 matrix
is this.

\begin{matrix}| \begin{matrix}{t}_{1 , 1} & {t}_{1 , 2} & {t}_{1 , 3} \\ {t}_{2 , 1} & {t}_{2 , 2} & {t}_{2 , 3} \\ {t}_{3 , 1} & {t}_{3 , 2} & {t}_{3 , 3}\end{matrix} | & = \begin{matrix} & {t}_{1 , 1} {t}_{2 , 2} {t}_{3 , 3} | {P}_{{ϕ}_{1}} | + {t}_{1 , 1} {t}_{2 , 3} {t}_{3 , 2} | {P}_{{ϕ}_{2}} | + {t}_{1 , 2} {t}_{2 , 1} {t}_{3 , 3} | {P}_{{ϕ}_{3}} | \\ & \ + {t}_{1 , 2} {t}_{2 , 3} {t}_{3 , 1} | {P}_{{ϕ}_{4}} | + {t}_{1 , 3} {t}_{2 , 1} {t}_{3 , 2} | {P}_{{ϕ}_{5}} | + {t}_{1 , 3} {t}_{2 , 2} {t}_{3 , 1} | {P}_{{ϕ}_{6}} |\end{matrix} \\ & = \begin{matrix} & {t}_{1 , 1} {t}_{2 , 2} {t}_{3 , 3} − {t}_{1 , 1} {t}_{2 , 3} {t}_{3 , 2} − {t}_{1 , 2} {t}_{2 , 1} {t}_{3 , 3} \\ & \ + {t}_{1 , 2} {t}_{2 , 3} {t}_{3 , 1} + {t}_{1 , 3} {t}_{2 , 1} {t}_{3 , 2} − {t}_{1 , 3} {t}_{2 , 2} {t}_{3 , 1}\end{matrix}\end{matrix}

Computing a determinant by permutation expansion usually takes longer than
Gauss' method.
However, here we are not trying to do the computation efficiently,
we are instead
trying to give a determinant formula that we can prove to be well-defined.
While the permutation expansion is impractical for computations,
it is useful in proofs.
In particular, we can use it for the result that we are after.

Theorem 3.11

For each n there is a n \ × \ n determinant function.

The proof is deferred to the following subsection.
Also there is the proof of the next result (they share some features).

Theorem 3.12

The determinant of a matrix equals the determinant of its transpose.

The consequence of this theorem is that,
while we have so far stated results in terms of rows
(e.g., determinants are multilinear in their rows, row swaps change the
signum, etc.),
all of the results also hold in terms of columns.
The final result gives examples.

Corollary 3.13

A matrix with two equal columns is singular. Column swaps change the sign of a determinant. Determinants are multilinear in their columns.

Proof

For the first statement, transposing the matrix results in a matrix with the same determinant, and with two equal rows, and hence a determinant of zero. The other two are proved in the same way.

We finish with a summary
(although the final subsection contains the unfinished business of
proving the two theorems).
Determinant functions exist, are unique, and we know how to compute them.
As for what determinants are about, perhaps these lines
(Kemp 1982) help make it memorable.

Determinant none,

Solution: lots or none.

Determinant some,

Solution: just one.

Exercises

These summarize the notation used in this book for the 2- and 3- permutations.

\begin{matrix}i & 1 & 2 \\ {ϕ}_{1} ( i ) & 1 & 2 \\ {ϕ}_{2} ( i ) & 2 & 1\end{matrix} \ \begin{matrix}i & 1 & 2 & 3 \\ {ϕ}_{1} ( i ) & 1 & 2 & 3 \\ {ϕ}_{2} ( i ) & 1 & 3 & 2 \\ {ϕ}_{3} ( i ) & 2 & 1 & 3 \\ {ϕ}_{4} ( i ) & 2 & 3 & 1 \\ {ϕ}_{5} ( i ) & 3 & 1 & 2 \\ {ϕ}_{6} ( i ) & 3 & 2 & 1\end{matrix}

This exercise is recommended for all readers.

Problem 1

Compute the determinant by using the permutation expansion.

| \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{matrix} |

| \begin{matrix}2 & 2 & 1 \\ 3 & − 1 & 0 \\ − 2 & 0 & 5\end{matrix} |

This exercise is recommended for all readers.

Problem 2

Compute these both with Gauss' method and with the permutation
expansion formula.

• | \begin{matrix}2 & 1 \\ 3 & 1\end{matrix} |
• | \begin{matrix}0 & 1 & 4 \\ 0 & 2 & 3 \\ 1 & 5 & 1\end{matrix} |

This exercise is recommended for all readers.

Problem 3

Use the permutation expansion formula to derive
the formula for {}3 \ × \ 3 determinants.

Problem 4

List all of the 4-permutations.

Problem 5

A permutation, regarded as a function from the set
\{ 1 , .. , n \} to itself, is one-to-one and onto.
Therefore, each permutation has an inverse.

• Find the inverse of each 2-permutation.
• Find the inverse of each 3-permutation.

Problem 6

Prove that f is multilinear if and only if for all
\overset{→}{v} , \overset{→}{w} ∈ V and {k}_{1} , {k}_{2} ∈ ℝ, this holds.

f ( {\overset{→}{ρ}}_{1} , … , {k}_{1} {\overset{→}{v}}_{1} + {k}_{2} {\overset{→}{v}}_{2} , … , {\overset{→}{ρ}}_{n} ) = {k}_{1} f ( {\overset{→}{ρ}}_{1} , … , {\overset{→}{v}}_{1} , … , {\overset{→}{ρ}}_{n} ) + {k}_{2} f ( {\overset{→}{ρ}}_{1} , … , {\overset{→}{v}}_{2} , … , {\overset{→}{ρ}}_{n} )

Problem 7

Find the only nonzero term in the permutation expansion of
this matrix.

| \begin{matrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0\end{matrix} |

Compute that determinant by finding the signum of the associated
permutation.

Problem 8

How would determinants change if we changed property (4) of the
definition to read that | I | = 2?

Problem 9

Verify the second and third
statements in Corollary 3.13.

This exercise is recommended for all readers.

Problem 10

Show that if an n \ × \ n matrix has a nonzero determinant
then any column vector
\overset{→}{v} ∈ {ℝ}^{n} can be expressed as a linear combination
of the columns of the matrix.

Problem 11

True or false: a matrix whose entries are only zeros or ones has a determinant equal to zero, one, or negative one. (Strang 1980)

Problem 12

• Show that there are 120 terms in the permutation
  expansion formula of a {}5 \ × \ 5 matrix.

How many are sure to be zero if the {}1 , 2 entry is zero?

Problem 13

How many n-permutations are there?

Problem 14

A matrix A is skew-symmetric if
{A}^{t r a n s} = − A, as in this matrix.

A = ( \begin{matrix}0 & 3 \\ − 3 & 0\end{matrix} )

Show that n \ × \ n skew-symmetric matrices with nonzero
determinants exist only for even n.

This exercise is recommended for all readers.

Problem 15

What is the smallest number of zeros, and the placement of
those zeros, needed to ensure that a {}4 \ × \ 4 matrix has a
determinant of zero?

This exercise is recommended for all readers.

Problem 16

If we have n data points
( {x}_{1} , {y}_{1} ) , ( {x}_{2} , {y}_{2} ) , … \ , ( {x}_{n} , {y}_{n} ) and want to find a
polynomial p ( x ) = {a}_{n − 1} {x}^{n − 1} + {a}_{n − 2} {x}^{n − 2} + … + {a}_{1} x + {a}_{0}
passing through those points
then we can plug in the points to get an n equation/n unknown
linear system.
The matrix of coefficients for that system is called the
Vandermonde matrix. Prove that the determinant of the transpose
of that matrix of coefficients

| \begin{matrix}1 & 1 & … & 1 \\ {x}_{1} & {x}_{2} & … & {x}_{n} \\ {{x}_{1}}^{2} & {{x}_{2}}^{2} & … & {{x}_{n}}^{2} \\ & ⋮ \\ {{x}_{1}}^{n − 1} & {{x}_{2}}^{n − 1} & … & {{x}_{n}}^{n − 1}\end{matrix} |

equals the product, over all indices i , j ∈ \{ 1 , … , n \} with
i < j, of terms of the form {x}_{j} − {x}_{i}.
(This shows that
the determinant is zero, and the linear system has no solution,
if and only if the {x}_{i}'s in the data are not distinct.)

Problem 17

A matrix can be divided into blocks, as here,

( \begin{matrix}1 & 2 & 0 \\ 3 & 4 & 0 \\ 0 & 0 & − 2\end{matrix} )

which shows four blocks, the square {}2 \ × \ 2 and {}1 \ × \ 1 ones
in the upper left and lower right, and the zero blocks in the
upper right and lower left.
Show that if a matrix can be partitioned as

T = ( \begin{matrix}J & {Z}_{2} \\ {Z}_{1} & K\end{matrix} )

where J and K are square, and {Z}_{1} and {Z}_{2} are all zeroes,
then | T | = | J | ⋅ | K |.

This exercise is recommended for all readers.

Problem 18

Prove that for any n \ × \ n matrix T there are at most
n distinct reals r such that the matrix T − r I has
determinant zero
(we shall use this result in Chapter Five).

? Problem 19

The nine positive digits can be arranged into {}3 \ × \ 3 arrays
in {}9 ! ways.
Find the sum of the determinants of these arrays. (Trigg 1963)

Problem 20

Show that

| \begin{matrix}x − 2 & x − 3 & x − 4 \\ x + 1 & x − 1 & x − 3 \\ x − 4 & x − 7 & x − 10\end{matrix} | = 0.

(Silverman & Trigg 1963)

? Problem 21

Let S be the sum of the integer elements of a magic square of order
three and let D be the value of the square considered as a
determinant.
Show that D / S is an integer.
(Trigg & Walker 1949)

? Problem 22

Show that the determinant of the {n}^{2} elements in the upper left
corner of the Pascal triangle

\begin{matrix}1 & 1 & 1 & 1 & . & . \\ 1 & 2 & 3 & . & . \\ 1 & 3 & . & . & & \\ 1 & . & . & & & \\ . \\ .\end{matrix}

has the value unity.
(Rupp & Aude 1931)

Solutions

References

• Kemp, Franklin (1982), "Linear Equations", American Mathematical Monthly, American Mathematical Society: 608 {{citation}}: Unknown parameter |month= ignored (help).
• Silverman, D. L. (proposer); Trigg, C. W. (solver) (1963), "Quickie 237", Mathematics Magazine, 36 (1), American Mathematical Society {{citation}}: Unknown parameter |month= ignored (help).
• Strang, Gilbert (1980), Linear Algebra and its Applications (2nd ed.), Hartcourt Brace Javanovich
• Trigg, C. W. (proposer) (1963), "Quickie 307", Mathematics Magazine, 36 (1), American Mathematical Society: 77 {{citation}}: Unknown parameter |month= ignored (help).
• Trigg, C. W. (proposer); Walker, R. J. (solver) (1949), "Elementary Problem 813", American Mathematical Monthly, 56 (1), American Mathematical Society {{citation}}: Unknown parameter |month= ignored (help).
• Rupp, C. A. (proposer); Aude, H. T. R. (solver) (1931), "Problem 3468", American Mathematical Monthly, 37 (6), American Mathematical Society: 355 {{citation}}: Unknown parameter |month= ignored (help).

Where this page came from

This page was imported from Wikibooks. From “Linear Algebra” on Wikibooks, by its contributors, under CC BY-SA 4.0. Changed here: set as a page; navigation and edit links left out; each image under its own licence, credited in its caption.

Nobody has written it yet — it is the source material at a new address, which is why search engines are asked to skip it and why no one earns from it. It is up for grabs: take it on, and it is yours to rewrite and to earn from.