Linear Algebra/The Permutation Expansion/Solutions

Solutions

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

${\begin{array}{c|cc}i&1&2\\\hline \phi _{1}(i)&1&2\\\phi _{2}(i)&2&1\end{array}}\qquad {\begin{array}{c|ccc}i&1&2&3\\\hline \phi _{1}(i)&1&2&3\\\phi _{2}(i)&1&3&2\\\phi _{3}(i)&2&1&3\\\phi _{4}(i)&2&3&1\\\phi _{5}(i)&3&1&2\\\phi _{6}(i)&3&2&1\end{array}}$

This exercise is recommended for all readers.

Problem 1

Compute the determinant by using the permutation expansion.

1. ${\begin{vmatrix}1&2&3\\4&5&6\\7&8&9\end{vmatrix}}$
2. ${\begin{vmatrix}2&2&1\\3&-1&0\\-2&0&5\end{vmatrix}}$

Answer

1. This matrix is singular.

   ${\begin{array}{rl}{\begin{vmatrix}1&2&3\\4&5&6\\7&8&9\end{vmatrix}}&={\begin{aligned}&(1)(5)(9)\left|P_{\phi _{1}}\right|+(1)(6)(8)\left|P_{\phi _{2}}\right|+(2)(4)(9)\left|P_{\phi _{3}}\right|\\&\quad +(2)(6)(7)\left|P_{\phi _{4}}\right|+(3)(4)(8)\left|P_{\phi _{5}}\right|+(7)(5)(3)\left|P_{\phi _{6}}\right|\end{aligned}}\\&=0\end{array}}$

2. This matrix is nonsingular.

   ${\begin{array}{rl}{\begin{vmatrix}2&2&1\\3&-1&0\\-2&0&5\end{vmatrix}}&={\begin{aligned}&(2)(-1)(5)\left|P_{\phi _{1}}\right|+(2)(0)(0)\left|P_{\phi _{2}}\right|+(2)(3)(5)\left|P_{\phi _{3}}\right|\\&\quad +(2)(0)(-2)\left|P_{\phi _{4}}\right|+(1)(3)(0)\left|P_{\phi _{5}}\right|+(-2)(-1)(1)\left|P_{\phi _{6}}\right|\end{aligned}}\\&=-42\end{array}}$

This exercise is recommended for all readers.

Problem 2

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

1. ${\begin{vmatrix}2&1\\3&1\end{vmatrix}}$
2. ${\begin{vmatrix}0&1&4\\0&2&3\\1&5&1\end{vmatrix}}$

Answer

1. Gauss' method gives this

   ${\begin{vmatrix}2&1\\3&1\end{vmatrix}}={\begin{vmatrix}2&1\\0&-1/2\end{vmatrix}}=-1$

   and permutation expansion gives this.

   ${\begin{vmatrix}2&1\\3&1\end{vmatrix}}={\begin{vmatrix}2&0\\0&1\end{vmatrix}}+{\begin{vmatrix}0&1\\3&0\end{vmatrix}}=(2)(1){\begin{vmatrix}1&0\\0&1\end{vmatrix}}+(1)(3){\begin{vmatrix}0&1\\1&0\end{vmatrix}}=-1$

2. Gauss' method gives this

   ${\begin{vmatrix}0&1&4\\0&2&3\\1&5&1\end{vmatrix}}=-{\begin{vmatrix}1&5&1\\0&2&3\\0&1&4\end{vmatrix}}=-{\begin{vmatrix}1&5&1\\0&2&3\\0&0&5/2\end{vmatrix}}=-5$

   and the permutation expansion gives this.

   ${\begin{array}{rl}{\begin{vmatrix}0&1&4\\0&2&3\\1&5&1\end{vmatrix}}&={\begin{aligned}&(0)(2)(1)\left|P_{\phi _{1}}\right|+(0)(3)(5)\left|P_{\phi _{2}}\right|+(1)(0)(1)\left|P_{\phi _{3}}\right|\\&\quad +(1)(3)(1)\left|P_{\phi _{4}}\right|+(4)(0)(5)\left|P_{\phi _{5}}\right|+(1)(2)(0)\left|P_{\phi _{6}}\right|\end{aligned}}\\&=-5\end{array}}$

This exercise is recommended for all readers.

Problem 3

Use the permutation expansion formula to derive the formula for $3\!\times \!3$ determinants.

Answer

Following Example 3.6 gives this.

${\begin{array}{rl}{\begin{vmatrix}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{vmatrix}}&={\begin{aligned}&t_{1,1}t_{2,2}t_{3,3}\left|P_{\phi _{1}}\right|+t_{1,1}t_{2,3}t_{3,2}\left|P_{\phi _{2}}\right|\\&\quad +t_{1,2}t_{2,1}t_{3,3}\left|P_{\phi _{3}}\right|+t_{1,2}t_{2,3}t_{3,1}\left|P_{\phi _{4}}\right|\\&\quad +t_{1,3}t_{2,1}t_{3,2}\left|P_{\phi _{5}}\right|+t_{1,3}t_{2,2}t_{3,1}\left|P_{\phi _{6}}\right|\end{aligned}}\\&={\begin{aligned}&t_{1,1}t_{2,2}t_{3,3}(+1)+t_{1,1}t_{2,3}t_{3,2}(-1)\\&\quad +t_{1,2}t_{2,1}t_{3,3}(-1)+t_{1,2}t_{2,3}t_{3,1}(+1)\\&\quad +t_{1,3}t_{2,1}t_{3,2}(+1)+t_{1,3}t_{2,2}t_{3,1}(-1)\end{aligned}}\end{array}}$

Problem 4

List all of the $4$-permutations.

Answer

This is all of the permutations where $\phi (1)=1$

${\begin{array}{rl}&\phi _{1}=\langle 1,2,3,4\rangle \quad \phi _{2}=\langle 1,2,4,3\rangle \quad \phi _{3}=\langle 1,3,2,4\rangle \\&\quad \phi _{4}=\langle 1,3,4,2\rangle \quad \phi _{5}=\langle 1,4,2,3\rangle \quad \phi _{6}=\langle 1,4,3,2\rangle \end{array}}$

the ones where $\phi (1)=1$

${\begin{array}{rl}&\phi _{7}=\langle 2,1,3,4\rangle \quad \phi _{8}=\langle 2,1,4,3\rangle \quad \phi _{9}=\langle 2,3,1,4\rangle \\&\quad \phi _{10}=\langle 2,3,4,1\rangle \quad \phi _{11}=\langle 2,4,1,3\rangle \quad \phi _{12}=\langle 2,4,3,1\rangle \end{array}}$

the ones where $\phi (1)=3$

${\begin{array}{rl}&\phi _{13}=\langle 3,1,2,4\rangle \quad \phi _{14}=\langle 3,1,4,2\rangle \quad \phi _{15}=\langle 3,2,1,4\rangle \\&\quad \phi _{16}=\langle 3,2,4,1\rangle \quad \phi _{17}=\langle 3,4,1,2\rangle \quad \phi _{18}=\langle 3,4,2,1\rangle \end{array}}$

and the ones where $\phi (1)=4$.

${\begin{array}{rl}&\phi _{19}=\langle 4,1,2,3\rangle \quad \phi _{20}=\langle 4,1,3,2\rangle \quad \phi _{21}=\langle 4,2,1,3\rangle \\&\quad \phi _{22}=\langle 4,2,3,1\rangle \quad \phi _{23}=\langle 4,3,1,2\rangle \quad \phi _{24}=\langle 4,3,2,1\rangle \end{array}}$

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.

1. Find the inverse of each $2$-permutation.
2. Find the inverse of each $3$-permutation.

Answer

Each of these is easy to check.

1. permutation	$\phi _{1}$	$\phi _{2}$
   inverse	$\phi _{1}$	$\phi _{2}$

2. permutation	$\phi _{1}$	$\phi _{2}$	$\phi _{3}$	$\phi _{4}$	$\phi _{5}$	$\phi _{6}$
   inverse	$\phi _{1}$	$\phi _{2}$	$\phi _{3}$	$\phi _{5}$	$\phi _{4}$	$\phi _{6}$

Problem 6

Prove that $f$ is multilinear if and only if for all ${\vec {v}},{\vec {w}}\in V$ and $k_{1},k_{2}\in \mathbb {R}$, this holds.

$f({\vec {\rho }}_{1},\dots ,k_{1}{\vec {v}}_{1}+k_{2}{\vec {v}}_{2},\dots ,{\vec {\rho }}_{n})=k_{1}f({\vec {\rho }}_{1},\dots ,{\vec {v}}_{1},\dots ,{\vec {\rho }}_{n})+k_{2}f({\vec {\rho }}_{1},\dots ,{\vec {v}}_{2},\dots ,{\vec {\rho }}_{n})$

Answer

For the "if" half, the first condition of Definition 3.2 follows from taking $k_{1}=k_{2}=1$ and the second condition follows from taking $k_{2}=0$.

The "only if" half also routine. From $f({\vec {\rho }}_{1},\dots ,k_{1}{\vec {v}}_{1}+k_{2}{\vec {v}}_{2},\dots ,{\vec {\rho }}_{n})$ the first condition of Definition 3.2 gives $=f({\vec {\rho }}_{1},\dots ,k_{1}{\vec {v}}_{1},\dots ,{\vec {\rho }}_{n})+f({\vec {\rho }}_{1},\dots ,k_{2}{\vec {v}}_{2},\dots ,{\vec {\rho }}_{n})$ and the second condition, applied twice, gives the result.

Problem 7

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

${\begin{vmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{vmatrix}}$

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

Answer

To get a nonzero term in the permutation expansion we must use the $1,2$ entry and the $4,3$ entry. Having fixed on those two we must also use the $2,1$ entry and the $3,4$ entry. The signum of $\langle 2,1,4,3\rangle$ is $+1$ because from

${\begin{pmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}}$

the two row swaps $\rho _{1}\leftrightarrow \rho _{2}$ and $\rho _{3}\leftrightarrow \rho _{4}$ will produce the identity matrix.

Problem 8

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

Answer

They would all double.

Problem 9

Verify the second and third statements in Corollary 3.13.

Answer

For the second statement, given a matrix, transpose it, swap rows, and transpose back. The result is swapped columns, and the determinant changes by a factor of $-1$. The third statement is similar: given a matrix, transpose it, apply multilinearity to what are now rows, and then transpose back the resulting matrices.

This exercise is recommended for all readers.

Problem 10

Show that if an $n\!\times \!n$ matrix has a nonzero determinant then any column vector ${\vec {v}}\in \mathbb {R} ^{n}$ can be expressed as a linear combination of the columns of the matrix.

Answer

An $n\!\times \!n$ matrix with a nonzero determinant has rank $n$ so its columns form a basis for $\mathbb {R} ^{n}$.

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)

Answer

False.

${\begin{vmatrix}1&-1\\1&1\end{vmatrix}}=2$

Problem 12

1. Show that there are $120$ terms in the permutation expansion formula of a $5\!\times \!5$ matrix.
2. How many are sure to be zero if the $1,2$ entry is zero?

Answer

1. For the column index of the entry in the first row there are five choices. Then, for the column index of the entry in the second row there are four choices (the column index used in the first row cannot be used here). Continuing, we get $5\cdot 4\cdot 3\cdot 2\cdot 1=120$. (See also the next question.)
2. Once we choose the second column in the first row, we can choose the other entries in $4\cdot 3\cdot 2\cdot 1=24$ ways.

Problem 13

How many $n$-permutations are there?

Answer

$n\cdot (n-1)\cdots 2\cdot 1=n!$

Problem 14

A matrix $A$ is skew-symmetric if ${{A}^{\rm {trans}}}=-A$, as in this matrix.

$A={\begin{pmatrix}0&3\\-3&0\end{pmatrix}}$

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

Answer

In $\left|A\right|=\left|{{A}^{\rm {trans}}}\right|=\left|-A\right|=(-1)^{n}\left|A\right|$ the exponent $n$ must be even.

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\!\times \!4$ matrix has a determinant of zero?

Answer

Showing that no placement of three zeros suffices is routine. Four zeroes does suffice; put them all in the same row or column.

This exercise is recommended for all readers.

Problem 16

If we have $n$ data points $(x_{1},y_{1}),(x_{2},y_{2}),\dots \,,(x_{n},y_{n})$ and want to find a polynomial $p(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\dots +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{vmatrix}1&1&\ldots &1\\x_{1}&x_{2}&\ldots &x_{n}\\{x_{1}}^{2}&{x_{2}}^{2}&\ldots &{x_{n}}^{2}\\&\vdots \\{x_{1}}^{n-1}&{x_{2}}^{n-1}&\ldots &{x_{n}}^{n-1}\end{vmatrix}}$

equals the product, over all indices $i,j\in \{1,\dots ,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.)

Answer

The $n=3$ case shows what to do. The pivot operations of $-x_{1}\rho _{2}+\rho _{3}$ and $-x_{1}\rho _{1}+\rho _{2}$ give this.

${\begin{vmatrix}1&1&1\\x_{1}&x_{2}&x_{3}\\x_{1}^{2}&x_{2}^{2}&x_{3}^{2}\end{vmatrix}}={\begin{vmatrix}1&1&1\\x_{1}&x_{2}&x_{3}\\0&(-x_{1}+x_{2})x_{2}&(-x_{1}+x_{3})x_{3}\end{vmatrix}}={\begin{vmatrix}1&1&1\\0&-x_{1}+x_{2}&-x_{1}+x_{3}\\0&(-x_{1}+x_{2})x_{2}&(-x_{1}+x_{3})x_{3}\end{vmatrix}}$

Then the pivot operation of $x_{2}\rho _{2}+\rho _{3}$ gives the desired result.

$={\begin{vmatrix}1&1&1\\0&-x_{1}+x_{2}&-x_{1}+x_{3}\\0&0&(-x_{1}+x_{3})(-x_{2}+x_{3})\end{vmatrix}}=(x_{2}-x_{1})(x_{3}-x_{1})(x_{3}-x_{2})$

Problem 17

A matrix can be divided into blocks, as here,

$\left({\begin{array}{cc|c}1&2&0\\3&4&0\\\hline 0&0&-2\end{array}}\right)$

which shows four blocks, the square $2\!\times \!2$ and $1\!\times \!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=\left({\begin{array}{c|c}J&Z_{2}\\\hline Z_{1}&K\end{array}}\right)$

where $J$ and $K$ are square, and $Z_{1}$ and $Z_{2}$ are all zeroes, then $\left|T\right|=\left|J\right|\cdot \left|K\right|$.

Answer

Let $T$ be $n\!\times \!n$, let $J$ be $p\!\times \!p$, and let $K$ be $q\!\times \!q$. Apply the permutation expansion formula

$\sum _{{\text{permutations }}\phi }$

$\left|T\right|=\sum _{{\text{permutations }}\phi }t_{1,\phi (1)}t_{2,\phi (2)}\dots t_{n,\phi (n)}\left|P_{\phi }\right|$

Because the upper right of $T$ is all zeroes, if a $\phi$ has at least one of $p+1,\dots ,n$ among its first $p$ column numbers $\phi (1),\dots ,\phi (p)$ then the term arising from $\phi$ is $0$ (e.g., if $\phi (1)=n$ then $t_{1,\phi (1)}t_{2,\phi (2)}\dots t_{n,\phi (n)}$ is $0$). So the above formula reduces to a sum over all permutations with two halves: first $1,\dots ,p$ are rearranged, and after that comes a permutation of $p+1,\dots ,p+q$. To see this gives $\left|J\right|\cdot \left|K\right|$, distribute.

${\bigg [}\sum _{\begin{array}{c}\\[-19pt]\scriptstyle {\text{perms }}\phi _{1}\\[-5pt]\scriptstyle {\text{of }}1,\dots ,p\end{array}}t_{1,\phi _{1}(1)}\cdots t_{p,\phi _{1}(p)}\left|P_{\phi _{1}}\right|{\bigg ]}\cdot {\bigg [}\sum _{\begin{array}{c}\\[-19pt]\scriptstyle {\text{perms }}\phi _{2}\\[-5pt]\scriptstyle {\text{of }}p+1,\dots ,p+q\end{array}}t_{p+1,\phi _{2}(p+1)}\cdots t_{p+q,\phi _{2}(p+q)}\left|P_{\phi _{2}}\right|{\bigg ]}$

This exercise is recommended for all readers.

Problem 18

Prove that for any $n\!\times \!n$ matrix $T$ there are at most $n$ distinct reals $r$ such that the matrix $T-rI$ has determinant zero (we shall use this result in Chapter Five).

Answer

The $n=3$ case shows what happens.

$\left|T-rI\right|={\begin{vmatrix}t_{1,1}-x&t_{1,2}&t_{1,3}\\t_{2,1}&t_{2,2}-x&t_{2,3}\\t_{3,1}&t_{3,2}&t_{3,3}-x\end{vmatrix}}$

Each term in the permutation expansion has three factors drawn from entries in the matrix (e.g., $(t_{1,1}-x)(t_{2,2}-x)(t_{3,3}-x)$ and $(t_{1,1}-x)(t_{2,3})(t_{3,2})$), and so the determinant is expressible as a polynomial in $x$ of degree $3$. Such a polynomial has at most $3$ roots.

In general, the permutation expansion shows that the determinant can be written as a sum of terms, each with $n$ factors, giving a polynomial of degree $n$. A polynomial of degree $n$ has at most $n$ roots.

? Problem 19

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

Answer

This is how the answer was given in the cited source.

When two rows of a determinant are interchanged, the sign of the determinant is changed. When the rows of a three-by-three determinant are permuted, $3$ positive and $3$ negative determinants equal in absolute value are obtained. Hence the $9!$ determinants fall into $9!/6$ groups, each of which sums to zero.

Problem 20

Show that

${\begin{vmatrix}x-2&x-3&x-4\\x+1&x-1&x-3\\x-4&x-7&x-10\end{vmatrix}}=0.$

(Silverman & Trigg 1963)

Answer

This is how the answer was given in the cited source.

When the elements of any column are subtracted from the elements of each of the other two, the elements in two of the columns of the derived determinant are proportional, so the determinant vanishes. That is,

${\begin{vmatrix}2&1&x-4\\4&2&x-3\\6&3&x-10\end{vmatrix}}={\begin{vmatrix}1&x-3&-1\\2&x-1&-2\\3&x-7&-3\end{vmatrix}}={\begin{vmatrix}x-2&-1&-2\\x+1&-2&-4\\x-4&-3&-6\end{vmatrix}}=0.$

? 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)

Answer

This is how the answer was given in the cited source.

Let

${\begin{array}{ccc}a&b&c\\d&e&f\\g&h&i\end{array}}$

have magic sum $N=S/3$. Then

${\begin{array}{rl}N&=(a+e+i)+(d+e+f)+(g+e+c)\\&\quad -(a+d+g)-(c+f+i)=3e\end{array}}$

and $S=9e$. Hence, adding rows and columns,

$D={\begin{vmatrix}a&b&c\\d&e&f\\g&h&i\end{vmatrix}}={\begin{vmatrix}a&b&c\\d&e&f\\3e&3e&3e\end{vmatrix}}={\begin{vmatrix}a&b&3e\\d&e&3e\\3e&3e&9e\end{vmatrix}}={\begin{vmatrix}a&b&e\\d&e&e\\1&1&1\end{vmatrix}}S.$

? Problem 22

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

${\begin{array}{cccccc}1&1&1&1&.&.\\1&2&3&.&.\\1&3&.&.&&\\1&.&.&&&\\.\\.\end{array}}$

has the value unity. (Rupp & Aude 1931)

Answer

This is how the answer was given in the cited source. Denote by $D_{n}$ the determinant in question and by $a_{i,j}$ the element in the $i$-th row and $j$-th column. Then from the law of formation of the elements we have

$a_{i,j}=a_{i,j-1}+a_{i-1,j},\qquad a_{1,j}=a_{i,1}=1.$

Subtract each row of $D_{n}$ from the row following it, beginning the process with the last pair of rows. After the $n-1$ subtractions the above equality shows that the element $a_{i,j}$ is replaced by the element $a_{i,j-1}$, and all the elements in the first column, except $a_{1,1}=1$, become zeroes. Now subtract each column from the one following it, beginning with the last pair. After this process the element $a_{i,j-1}$ is replaced by $a_{i-1,j-1}$, as shown in the above relation. The result of the two operations is to replace $a_{i,j}$ by $a_{i-1,j-1}$, and to reduce each element in the first row and in the first column to zero. Hence $D_{n}=D_{n+i}$ and consequently

$D_{n}=D_{n-1}=D_{n-2}=\dots =D_{2}=1.$

References

• Silverman, D. L. (proposer); Trigg, C. W. (solver) (Jan. 1963), "Quickie 237", Mathematics Magazine (American Mathematical Society) 36 (1) .
• Strang, Gilbert (1980), Linear Algebra and its Applications (2nd ed.), Hartcourt Brace Javanovich 
• Trigg, C. W. (proposer) (Jan. 1963), "Quickie 307", Mathematics Magazine (American Mathematical Society) 36 (1): 77 .
• Trigg, C. W. (proposer); Walker, R. J. (solver) (Jan. 1949), "Elementary Problem 813", American Mathematical Monthly (American Mathematical Society) 56 (1) .
• Rupp, C. A. (proposer); Aude, H. T. R. (solver) (Jun.-July 1931), "Problem 3468", American Mathematical Monthly (American Mathematical Society) 37 (6): 355 .