A challenge question in determinant of real matrices!

Question

Suppose that $n\in \mathbb N -\{1\}$ and $a_{11},a_{12},\ldots,a_{nn}$ are $n^2$ distinct real numbers, prove that there is some enumeration of $a_{ij}$'s like $b_{ij}\ (i,j=1,2,\ldots,n)$ such that,the determinant of the matrix $B=[b_{ij}]$ isn't zero!

Answer 1

Having seen your previous question, here is an answer that follows your line of reasoning. The following is the missing piece:

Lemma. If the sequence $b_1,b_2,\ldots,b_n$ is strictly monotone and its entries are all nonpositive or all nonnegative, the circulant matrix $C$ with $(b_1,b_2,\ldots,b_n)$ on the first row is nonsingular.

For a proof of the above lemma, see, e.g. proposition 24 on p.374 of Irwin Kra and Santiago R. Simanca, On Circulant Matrices, Notices of the AMS, March 2012 (official link).

Now, put all entries of $A$ in a list, sort the list in ascending order and partition the sorted list into $n$ sublists of equal lengths.

Since all entries of $A$ are distinct real numbers, at most one sublist contains entries of different signs. If such a sublist exists, put its entries (in any order) into the first column of $B$. Otherwise, just take any sublist at will and put its entries into the first column.

We then fill in the remaining columns one by one. By the above lemma, the circulant matrix $C$ generated by each remaining sorted sublist is nonsingular. Therefore, we can always pick a column of $C$ that is linearly independent with the previously filled columns of $B$, and let it be the next new column of $B$.