Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I'm not sure if I understand correctly? Is the question how many zeros can we add in a generic 4x4-matrix to make the determinant zero? –  Fredrik Meyer Nov 19 '12 at 15:16
    
In question two, what is being counted? Total number of 0's and 1's? –  rschwieb Nov 19 '12 at 15:22
    
Helo Fredrik. I make copy and paste of the book of Strang. Also I'm not sure if I understand correctly. –  zacarias Nov 19 '12 at 15:23
6  
In my copy of Strang, the second question requires the determinant to be one, not zero. Then a natural candidate to consider would be a triangular matrix with 4 ones on the main diagonal. –  Per Manne Nov 19 '12 at 15:27
    
Thank you Per Manne. I had made a mistake, in fact is "one" anf not "zero" in the second question. –  zacarias Nov 19 '12 at 15:37

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
+1 for a very complete argument. Personally I would've been satisfied even without the last paragraph. –  EuYu Nov 19 '12 at 18:33

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.

share|improve this answer
    
+1 for explaining the reason why 4 are necessary. It is easy to construct examples to show that four zeros are necessary, but the theoretical reason makes us understand more. –  user1551 Nov 19 '12 at 17:14
    
@downvoter If there is anything incorrect or unclear, then please tell me. –  EuYu Nov 19 '12 at 18:20

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.

share|improve this answer
    
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$. –  EuYu Nov 19 '12 at 18:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.