Problem 2 - Determinants

1.

Define a $5 \times 5$ matrix $A_5$ by

$$A_5 = \left( \begin{tabular}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 ... ... 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ \end{tabular} \right)$$

Compute the determinant of $A_5$.

2.

Let $A$ be an $n \times n$ matrix such that its elements are 0 and 1, and in each column 1's appear consecutively. For example, the matrix $A_5$ is such a matrix. Find all possible values of the determinant of $A$ satisfying the condition.

3.

For this matrix $A$ and an $n$-dimensional vector $\boldsymbol{b}$, let $\boldsymbol{x}$ be an $n$-dimensional variable vector satisfying the linear system of equation $A \boldsymbol{x} = \boldsymbol{b}$. Show that each element of $\boldsymbol{x}$ is an integer if $A$ is nonsingular and all the elements of $\boldsymbol{b}$ are integers.

1.

$$det A_5 = \left\vert \begin{tabular}{ccccc} 1 & 0 & 0 & 0 & 0 \\ ... ...1 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ \end{tabular} \right\vert$$

$$= (-1)^{3+1} \left\vert \begin{tabular}{ccc} 1 & 1 & 1 \\ 0 & 1... ...ft\vert \begin{tabular}{cc} 1 & 1 \\ 0 & 1 \\ \end{tabular} \right\vert = 1$$

2.

We shall show by induction on the size of the (square) matrix $A_n$ that $\det(A_n)\in\{-1,0,1\}$.

This is obvious for $n=1$. For $n=2$, the determinant of $A_2$ will be of the form $ab-bc$ if the matrix is denoted:

$$A_2=\left(\begin{tabular}{cc} $a$ & $b$ \\ $c$ & $d$ \end{tabular}\right)$$

As the elements can be only 0 or 1, $\det(A_2)\in\{-1,0,1\}$.

Let us now assume that this property is true for $A_{n-1}$ and let us consider any $A_n$ matrix satisfying the definition above. We consider the first line of this matrix.

• If this line is filled with 0's, then $\det(A_n) = 0$.
• If this line is filled with 0's except for the first element which is a 1, we can develop the determinant so that $\det(A_n) = \det(A_{n-1})$, which belongs to $\{-1,0,1\}$ according to the inductive hypothesis.
• If this line is randomly filled with 0's and 1's, we can make operations on some columns with other columns (addition, subtraction) so that after a finite number of operations we find ourselves in the previous case without changing the value of the determinant of $A_n$.

Thus, we have inductively proven that $\forall n\in \mathbb{N},\det(A_n)\in\{-1,0,1\}$.

3.

We have the following system of linear equations:

$$Ax=b$$

$A$ is nonsingular, thus we in fact face a Cramer system whose solution is given by the formula:

$$\forall j=1,2,\dots,n, x_j = \frac{\det(A_j(b))}{\det(A)}$$

where $x_j$ is the $j$th coordinate of $x$ and $A_j(b)$ is the matrix $A$ whose $j$th column has been replaced with $b$. As $A$ is nonsingular, we know that $\det(A)\in\{-1,1\}$ and by definition, we know that $\det(A_j(b)) = \sum_{\sigma\in\mathcal{S}_n \epsilon(\sigma)}\Pi_{i=1}^n a_{\sigma(i),i}$ where $\mathcal{S}_n$ is the set of $n$-permutations, $\epsilon$ the signature function and $a_{i,j}$ the elements of the matrix. As these elements are only integers and that the determinant id divided by 1 or $-1$, $\forall j=1,2,\dots,n, j\in \mathbb{Z}$.