4
$\begingroup$

These questions are of Gilbert Strang. Linear Algebra

1) Where can you put zeros in a 4 by 4 matrix, using as few as possible but enough to guarantee that the determinant is zero?

2) Where can you put zeros and ones in a 4 by 4 matrix, using as few as possible but enough to guarantee that the determinant is one?

For question 1 we can put 4 zeros on a line. So 4 zeros is enough. Is 4 the minimum?

and question 2?

  • 0
    Determinants of 4x4 matrices are linked with determinants of 3x3 matrices. Say you just put 3 $0$'s in a particular row of a 4x4 matrix, can you find a way to make the rest of the matrix have non-zero entries WHILST forcing the 4x4 matrix to have non-zero determinant?2012-11-19

3 Answers 3

2

I'll complete the argument that one cannot force a $n\times n$ determinant to be $1$ without fixing at least $\frac{n(n+1)}2$ of its entries, and with that number one must fix $n$ entries to $1$ and $\binom n2$ entries to $0$.

For the determinant to have a fixed value, all terms of the Leibniz formula must individually have a fixed value (since they all involve distinct monomials, and their sum is a constant polynomial). Clearly at least one fixed value must be $1$, arising for an even permutation $\sigma$. Then permuting the rows according to $\sigma$ we get another matrix with as many fixed entries, and the same value, and whose diagonal entries are all fixed to be $1$. Now for any $i\neq j$ neither of the entries $a_{i,j}$ and $a_{j,i}$ is fixed, we get a non-constant terms for $\sigma$ equal to the transposition of $i$ and $j$. So we must fix at least one of each of the $\binom n2$ such pairs of entries, proving we cannot succeed with less then $\frac{n(n+1)}2$ fixed entries. Moreover if we use exactly that number, then the entry fixed in each mentioned pair must be $0$ (or else the term for the transposition would still not be constant), so we have $n$ (diagonal) entries fixed to $1$ and $\binom n2$ (off-diagonal) entries fixed to $0$. Of course these entries could have been in different positions before permuting the rows.

Finally to show that we have essentially forced a triangular matrix, consider the oriented graph on the set $\{1,2,\ldots,n\}$, where there is an edge from $i$ to $j$ if $a_{i,j}$ is not fixed. Then this graph does not have oriented cycles, or else the term for that cyclic permutation would not be constant (the same argument we used for $2$-cycles). So the condition of having an oriented path from $i$ to $j$ defines a partial ordering of the points of the graph. This can be extended to a total ordering by adding directed edges, and it then has $\binom n2$ edges; but we supposed that there were $\binom n2$ unconstrained entries, so we had a total ordering from the outset. Now conjugating by the permutation that maps this total ordering to the natural ordering of $\{1,2,\ldots,n\}$ will make the matrix upper unitriangular.

  • 0
    +1 for a very complete argument. Personally I would've been satisfied even without the last paragraph.2012-11-19
1

For the first problem, $4$ zeroes are sufficient and necessary. Sufficiency is easily observed. For necessity, let us look at the Leibniz formula for the determinant $\det(A) = \sum_{\sigma \in S_4}\operatorname{sgn}(\sigma)\prod_{k=1}^4a_{k,\ \sigma(k)}$ If we place a zero in some entry $a_{i,j}$ then the summands of the determinant eliminated corresponds to the permutations for which $\sigma(i) = j$. There are $3!$ such permutations and so each zero we place eliminates at most $3!$ terms in the sum. There are a total of $4\times 3!$ total terms in the sum so at least $4$ zeroes are needed.

For the second problem, I highly suspect that the triangular matrix is optimal but I don't have a proof. We can either eliminate terms by placing zeroes or we can make a term $1$ by choosing all four entries corresponding to a term; we do not have the option to alter the values of the summands freely for non-trivial cancellation. Therefore the way to reach $\det(A) = 1$ is limited. We must have one non-zero term which is made $1$. Therefore we must have $4$ ones and enough zeroes to eliminate the $23$ other terms of the sum. In any case it doesn't seem that the same approach to problem 1 will be fruitful here. Perhaps someone else can finish off.

  • 0
    @downvoter I$f$ there is anything incorrect or unclear, then please tell me.2012-11-19
0

Question 1

Perhaps I'm missing something here. But you don't need any zeros for the determinant to be zero. All you need is for two of the rows, or two of the columns, to be linearly dependent. For example, if the first and second rows are the same then the matrix will have zero determinant. This is true for any $n \times n$ matrix with $n \ge 2$, not just $4 \times 4$. If you insist on having at least one zero then that's fine too. Put a zero in the top right and make sure that the first and second columns are the same.

This is because the determinant can be seen as a measure of area or volume. The determinant is the volume of the parallelepiped spanned by the columns or rows of the given matrix.

Question 2

Again, you don't need any zeros or ones. What about the matrix:

$\left[ \begin{array}{cccc} \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ -\frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{array}\right] . $

Just start with a matrix with the required area and then perform a Euclidean transformation.

  • 0
    I think the point of the question is that you don't have the freedom to choose the entries, only to make some of them $1$ and some of them $0$.2012-11-19