11
$\begingroup$

a) Assume that $(a_1, ..., a_9)$ are different positive numbers. Let us make a $3 \times 3$ matrix $A_s$ by placing them arbitrarily into $9$ positions available. Show that there is always a way to assemble them so that $\det(A_s) > 0$.

b) Assume now that some of $a_i, i =1,\dots,9$ are equal and the total number of different values taken by the $a_i$ is $N \in \{1,2,...,9\}$. What is the minimal $N$ which guarantees the existence of $A_s$ as above with $\det(A_s) >0$? Give a proof.

For part (a), I tried to show that, with row operations, $\det(A_s)$ can never equal $0$, so that the matrix is invertible, with determinant either negative or positive. Then if the determinant is positive, the proof is complete; if not, then simply interchange any two rows, which negates the determinant, giving a positive determinant as required. However, this proof doesn't work. Using just the numbers $1 \dots 9$, then $(7,8,9)$ is in the span of $(1,2,3)$ and $(4,5,6)$.

Since the question is asking to show that there is always a way, i.e., there exists a way to achieve $\det(A_s)>0$, I feel that I should work on a contradiction, and assume first that there is no way to achieve it.

Perhaps I can use the fact that $\rm{trace} \, A_s$ must be positive, but I don't see it right now.

Any hints would be greatly appreciated.

Thanks.

$\endgroup$
5
$\begingroup$

For part $(a)$ you are almost done. If $\mathrm{det}(A)=0$ and

$$A=\begin{bmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{bmatrix},$$ then $(a_1,a_2,a_3)=c_1(a_4, a_5, a_6)+c_2(a_7,a_8,a_9)$ for some $c_1,c_2 \in \mathbb{R}$. Note that $c_1, c_2 \neq 0$ by assumption since $a_i \neq a_j$ whenever $i \neq j$. By construction, we see that switching any two entries in any column ensures that the rank of the matrix will become $3$ and the the determinant will therefore be non-zero.

E.g., it is given that $a_1=c_1a_4+c_2a_7$. But if we switch $a_1$ with $a_4$, we can show that there cannot exist $c_3$ and $c_4$ such that $a_4=c_3a_1+c_4a_7$, $a_2= c_3a_5+c_4a_8$, and $a_3=c_3a_6+c_4a_9$ unless either $c_1=0$, $c_2=0$, $a_1=a_2$, $a_4=a_5$, or $a_8=a_9$. I leave this to you to verify. (Edit: as the OP pointed out to me in the comments below, I have also assumed here that the column vectors of $A$ were not scalar multiples. Thanks Lebron!). We now know how to rectify the situation where $\mathrm{det}(A)=0$. You have already demonstrated what to do if the determinant is negative, so the construction is complete.

For part $(b)$, we work backwards from the situation where $N=1$. Clearly, since there is but a single matrix we can construct and its determinant is zero, this is the degenerate case. Consider $N=2$. We now need to check only $4$ possible scenarios: when we can partition the set $\{a_i\}_{1\leq i \leq 9}$ into subsets of order $1$ and $8$ such that each element in each subset is redundant, the instance when such a partition into subsets creates subsets of order $2$ and $7$, then $3$ and $6$, and finally $4$ and $5$. We show that it is possible to end up in a situation where a matrix of non-zero determinant cannot be constructed.

Consider the instance when $a_i=a_j$ for all $1 \leq i,j \leq 8$ and $a_9$ is the distinct element. Then for every matrix, two rows are equal to one another and the rank is necessarily two.

Consider now when $N=3$. I claim that this is the minimum. In this case, there are only $7$ unique partitions of the set such that for each subset, all elements are redundant. The orders of the subsets in each instance are $$\{1,1,7\}, \{1,2,6\}, \{1,3,5\}, \{1,4,4\}, \{2,2,5\}, \{2,3,4\}, \text{and} \{3,3,3\}.$$

E.g, in the partition $\{1,3,5\}$, there is a number which only occurs once in the matrix, a number which occurs $3$ times, and a number which occurs $5$ times. Call the three distinct elements $a$, $b$, and $c$ and let the partition indicate the number of each: $\{\#a,\#b,\#c\}$. We will now show by construction that for each of the above partitions, a matrix of rank 3 exists.

For {1,1,7}:

\begin{bmatrix} a & c & c \\ c & b & c \\ c & c & c \end{bmatrix}

For {1,2,6}:

\begin{bmatrix} a & b & c \\ c & b & c \\ c & c & c \end{bmatrix}

For {1,3,5}:

\begin{bmatrix} a & b & c \\ c & b & c \\ c & b & c \end{bmatrix}

For {1,4,4}:

\begin{bmatrix} a & b & b \\ c & b & c \\ c & b & c \end{bmatrix}

For {2,2,5}:

\begin{bmatrix} a & a & b \\ c & b & c \\ c & c & c \end{bmatrix}

For {2,3,4}:

\begin{bmatrix} a & a & b \\ c & b & c \\ c & b & c \end{bmatrix}

For {3,3,3}:

\begin{bmatrix} a & b & a \\ c & c & b \\ b & a & c \end{bmatrix}

Phew! I enjoyed that, it was a very cool question and I have a feeling this is not the best way to go about proving this! Please let me know if you think I've made any mistakes here.

$\endgroup$
  • $\begingroup$ Hi @archaick: first off, thanks so much for writing up this solution :-) I think that for part(a), your idea is essentially correct, but possibly with one crucial modification needed. With your idea of swapping any two entries in any column, I then considered the Rank-Nullity Theorem. Look at the equation Ax = 0, and assume this equation is satisfied for some $(x_1,x_2,x_3)$, where the $x_i$ are not all 0. I.e., A has non-trivial null-space, is rank-deficient, and has determinant = 0. Now, consider any row of Ax, e.g., the first row is $a_1x_1 + a_2x_2 + a_3x_3$ = 0. $\endgroup$ – User001 Jul 24 '15 at 22:27
  • $\begingroup$ Using your idea, swap $a_1$ with $a_4$, but only if $x_1$ $\ne$ 0. (We are guaranteed that at least one of the $x_i$'s are non-zero, by assumption.) Then $a_4x_1 + a_2x_2 + a_3x_3$ $\ne$ 0, unless $(x_1,x_2,x_3)$ = (0,0,0), since the $a_i$'s are positive and different, which implies that the reassembled matrix A' has full rank, as required. (If you had swapped entries where the $x_i$ was zero, then the equations are still fulfilled, and A remains rank-deficient.) $\endgroup$ – User001 Jul 24 '15 at 22:27
  • $\begingroup$ @LebronJames Assume that $Ax=0$ for some $x=(x_1,x_2,x_3)\neq 0$. If swapping $a_1$ and $a_4$ doesn't remove $(x_1,x_2,x_3)$ from $ker(A)$, then, as you've observed $x_1=0$ but $\textbf{also } x_2=0$. But if $x_2=0$ then either $(a_7,a_8,a_9)=(0,0,0)$ or $x_3=0$ (i.e, $(x_1,x_2,x_3)=(0,0,0)$), a contradiction. $\endgroup$ – Archaick Jul 24 '15 at 22:41
  • $\begingroup$ Hi @Archaick, hmm... I agree that $x_1$ = 0, but why does $x_2$ = 0? We have $a_1(x_1 =0)$ + $a_5x_2$ + $a_6x_3$ = 0, by assumption, but I don't see any further restrictions on $x_2$ ... $\endgroup$ – User001 Jul 24 '15 at 22:55
  • $\begingroup$ @LebronJames Because you were right and I was wrong and I should check my work before I post it =D. I will edit the post, adding the caveat that the column vectors cannot be scalar multiples either. Thank you for pointing this out! $\endgroup$ – Archaick Jul 24 '15 at 23:07
4
$\begingroup$

Lemma. If positive numbers $a_1,a_2,a_3,a_4$ have at least two different values, then they can be put into a $2\times 2$ matrix so that the determinant is nonzero.

Proof: Suppose that $0 < a_1\leq a_2\leq a_3\leq a_4$, where not all the $a_i$'s are the same. Then $a_1a_2 < a_3 a_4$, so the matrix $\begin{bmatrix}a_3 & a_1 \\ a_2 & a_4\end{bmatrix}$ must have positive determinant.$\quad\square$

Theorem. If a sequence $a_1,\ldots,a_9$ of positive numbers has at least three different values, then they can be put into a $3\times 3$ matrix so that the determinant is nonzero.

Proof: Suppose $a_1,\ldots,a_9$ has at least three different values. If one of these values occurs seven times, then the matrix $$ \begin{bmatrix}a & c & c \\ c & b & c \\ c & c & c\end{bmatrix} $$ has determinant $c(a-c)(b-c)$, which is nonzero. Suppose then that no value occurs more than six times. Without loss of generality, we may assume that $a_1,a_2,a_3$ are all distinct and that $a_4,a_5,a_6,a_7$ are not all the same. By the lemma, it follows that $$ \left|\begin{matrix}a_4 & a_5 \\ a_6 & a_7\end{matrix}\right|\ne 0 $$ after a sufficient permutation of $a_4,a_5,a_6,a_7$. Now consider the following three matrices, which differ only in the first row. $$ A = \begin{bmatrix}a_1 & a_2 & a_3 \\ a_8 & a_4 & a_5 \\ a_9 & a_6 & a_7 \end{bmatrix},\qquad B = \begin{bmatrix}a_2 & a_3 & a_1 \\ a_8 & a_4 & a_5 \\ a_9 & a_6 & a_7 \end{bmatrix},\qquad C = \begin{bmatrix}a_3 & a_1 & a_2 \\ a_8 & a_4 & a_5 \\ a_9 & a_6 & a_7 \end{bmatrix}. $$ Since $a_1,a_2,a_3$ are distinct positive numbers, the vectors $(a_1,a_2,a_3)$, $(a_2,a_3,a_1)$, and $(a_3,a_1,a_2)$ are linearly independent. Then: $$ \lambda (a_1,a_2,a_3)+\mu(a_2,a_3,a_1)+\nu (a_3,a_1,a_3) = (a_1+a_2+a_3,0,0). $$ for some $\lambda,\mu,\nu\in\mathbb{R}$. Taking the dot product of this equation with the vector $(1,1,1)$ gives $$ (\lambda+\mu+\nu)(a_1+a_2+a_3) = a_1+a_2+a_3, $$ so $\lambda+\mu+\nu = 1$. It follows that $$ \lambda A +\mu B + \nu C \;=\; \begin{bmatrix}a_1+a_2+a_3 & 0 & 0 \\ a_8 & a_4 & a_5 \\ a_9 & a_6 & a_7 \end{bmatrix}, $$ so $|\lambda A+\mu B+\nu C| = (a_1+a_2+a_3)\left|\begin{matrix}a_4 & a_5 \\ a_6 & a_7\end{matrix}\right| \ne 0$. But, by the multilinearity of the determinant, $$ |\lambda A+\mu B + \nu C| \;=\; \lambda |A| + \mu |B| +\nu |C|, $$ so at least one of $|A|$, $|B|$, and $|C|$ must be nonzero.$\quad\square$

Note that $N=2$ does not suffice. In particular, if eight of the numbers are the same, then any matrix that you make will have at least two identical rows, so the determinant will be zero.

$\endgroup$
  • 1
    $\begingroup$ Nice answer! I think you might be able to simplify the last bit, though: Since $(a_1,a_2,a_3), (a_2,a_3,a_1), (a_3,a_1,a_2)$ are linearly independent, we have $\lambda,\mu, \nu$ such that $\lambda(a_1,a_2,a_3) + \mu(a_2,a_3,a_1) + \nu(a_3,a_1,a_2) = (1,0,0)$. Then just use multilinearity in the first row of the matrix, and you get $\lambda |A| + \mu |B| + \nu|C| = \begin{vmatrix} a_4 & a_5 \\ a_6 & a_7\end{vmatrix}$ $\endgroup$ – Alex Zorn Jul 24 '15 at 23:40
  • $\begingroup$ Thanks so much, @JimBelk, especially for your final note, which was crucial to my understanding of the question! Have a great night, professor :-) $\endgroup$ – User001 Jul 25 '15 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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