Order $n^2$ different reals, such that they form a $\mathbb{R^n}$ basis

Question

I've been trying to solve this linear algebra problem:

You are given $n^2 > 1$ pairwise different real numbers. Show that it's always possible to construct with them a basis for $\mathbb{R^n}$.

The problem seems to be intuitive enough, but I couldn't come up with a solution. I tried using the Leibniz formula for determinants, but I can't argument why I should be able to always arrange the numbers in such a way so that $det \ne 0$.

I also thought about first ordering the $n^2$ numbers, and then filling up a $n \times n$ matrix in a specific pattern, but I also couldn't close that argument.

Anyway, any help in the right direction would be appreciated :)!

Answer 1

We may prove the statement by mathematical induction. The base case $n=2$ is easy and we shall omit its proof. Suppose $n>2$. We call the target matrix $A$ and we partition it in the following way: \begin{align*} A=\left[ \begin{array}{ccccc} \pmatrix{|\\ |\\ \mathbf v_1\\ | \\ |} &\pmatrix{|\\ |\\ \mathbf v_2\\ | \\ |} &\cdots &\pmatrix{|\\ |\\ \mathbf v_n\\ | \\ |}\\ a_{n1}&a_{n2}&\cdots&a_{nn} \end{array} \right] \end{align*} where each $\mathbf v_j=(a_{1j},a_{2j},\ldots,a_{n-1,j})^\top$ is an $(n-1)$-dimensional vector.

By induction hypothesis, we may assume that the entries of the submatrix $M_{n1}=[\mathbf v_2,\ldots,\mathbf v_n]$ have been chosen so that $M_{n1}$ is nonsingular. Therefore, by deleting some row $\color{red}{k}$ of the submatrix $[\mathbf v_{\color{red}{3}},\ldots,\mathbf v_n]$, one can obtain an $(n-2)\times(n-2)$ nonsingular submatrix.

What does that mean? It means that by varying the choice of $a_{\color{red}{k}1}$, we can always pick $\mathbf v_1$ so that with $M_{n2}=[\mathbf v_1, \mathbf v_3,\ldots,\mathbf v_n]$, we have $\det M_{n2}\ne-\det M_{n1}$.

It remains to pick the entries of the last row of $A$ from the $n$ numbers left. By Laplace expansion, $(-1)^{n+1}\det A$ is equal to $$ a_{n1}\det M_{n1} - a_{n2}\det M_{n2} + \ldots\tag{1} $$ where the ellipses denote other summands that do not involve $a_{n1}$ or $a_{n2}$. If we swap the choices of $a_{n1}$ and $a_{n2}$, the signed determiant becomes $$ a_{n2}\det M_{n1} - a_{n1}\det M_{n2} + \ldots\tag{2} $$ instead. Since the difference between $(1)$ and $(2)$ is $(a_{n1}-a_{n2})(\det M_{n1}+\det M_{n2}) \ne 0$, we see that at least one set of choices would make $\det A$ nonzero.

Answer 2

You may want to use this lemma:

If $M$ is a $r\times s$ matrix with $s> r$ and the entries of $M$ are pairwise different, then there is a rearrangement of the first row such that the rank of the new matrix is $r$.

Proof: If the determinant of the minor formed by the first $r$ columns is $0$, just swap the entries at $(1,1)$ and $(1,r+1)$. Since these entries must be different, now the determinant of the same minor can't be $0$.

Now, apply the lemma to the $(n-1)\times n$ matrix obtained removing the first row, that is, rearrange the second row to ensure that some of the cofactors of the entries at the first row is not $0$.

So let be $x_1<\ldots<x_n$ the entries at the first row and $y_1,\ldots,y_n$ their respective cofactors. The determinant will be: $$x_1y_1+\cdots+x_ny_n$$ Since the values for $x_1,\ldots,x_n$ and for $y_1,\ldots,y_n$ are not all equal, you can apply the rearrangement inequality to guarrantee that , rearranging the entries at the first row by a permutation $\sigma$, the sum

$$x_{\sigma(1)}y_1+\cdots+x_{\sigma(n)}y_n$$

take at least two different values.