Is there a matrix of every size with all its submatrices invertible?

Question

Let's call a real matrix of size $m \times n$ totally invertible if for every $k$ rows and $k$ columns that we choose, we get an invertible matrix. I am curious about the following:

Is there a totally invertible matrix for all sizes $m \times n$?

By taking the transpose, we can assume $m \leq n$.

For $m=1$ we can take any vector in $\Bbb R^m$ without a zero entry.

For $m=2$ we can take $\begin{pmatrix} 1 &2 & 3 & ... &n \\ 2 & 3 & 4 & ... & n+1 \end{pmatrix}$. Indeed, $\det\begin{pmatrix} a &b \\ a+1 & b+1 \end{pmatrix}=a-b$ is nonzero when $a \neq b$. This does not generalize, since $a_{ij}=i+j-1$ fabulously fails for all submatrices of size $\geq 3$.

I also tried taking the rows to be $m$ of the cyclic shifts of the vector $(1,2, ... ,n)$. This does not work either because I found a $k=3, m=n=5$ counterexample.

I do feel that the answer should be positive, however. Is it?

Answer 1

If you only need an existential proof, just fill in the elements of an infinite matrix as follows. Set the first element to any nonzero real number. Then for every unfilled element, fill it by a number that is transcendental to the field of fractions generated by the previously filled elements (hence this new element is nonzero). Then any finite submatrix of this infinite matrix would be totally invertible.

There are also some meaningful classes of totally invertible matrices. E.g. any submatrix of a totally positive matrix is totally invertible. Some classes of totally positive matrices can be parametrised. See this set of slides entitled "The Grassmannian: total positivity" by Alexander Yong, for instance.

Answer 2

Yes, even with integer entries.

Note that if all of the entries of a $k\times k$ matrix are at most $M$ in absolute value, then its determinant is at most $k!M^k$ in absolute value. (This is because the determinant is a degree-$k$ polynomial in the entries of the matrix with $k!$ terms.)

It follows that if one entry of a $k\times k$ matrix is greater than $k!$ times the $k$th power of every other entry in absolute value, then the determinant can't possibly be $0$ (use a cofactor expansion along a row or column containing the big entry) and thus the matrix is invertible. Note: this isn't exactly right, but it is right if that entry's cofactor matrix is invertible. The construction below will have this property inductively.

Consequently, the $n\times n$ matrix $A=(a_{ij})$ defined by something like $$ a_{ij} = (n!+1)^{n^{i+j}} $$ is totally invertible: the lower right entry of every $k\times k$ submatrix is sufficiently larger than the other entries. (And of course, the $m\times n$ case follows from the $n\times n$ case.)

Answer 3

Given $m$ and $n$ there is only a finite number $N$ of possibilities to choose a positive $k\leq\min\{m,n\}$ and then $k$ rows and $k$ columns from an $m\times n$-matrix $X$ with variable entries $x_{jk}$ in order to obtain a quadratic submatrix $[S]$. Each such choice determines a polynomial $p(x):=\det[S]$ in the $m\cdot n$ variables $x_{jk}$, and the set $\{x\in{\mathbb R}^{m\cdot n}\>|\>p(x)=0\}$ is then a "variety" of dimension $mn-1$ in ${\mathbb R}^{m\cdot n}$. The union of these $N$ varieties has $m\cdot n$-dimensional Lebesgue measure $0$, which implies that "most" points $x\in{\mathbb R}^{m\cdot n}$, i.e., "most" $m\times n$-matrices $X$, will satisfy your condition.

Answer 4

Invertible Vandermonde matrices $V(a_1,a_2, \cdots, a_n)$ (https://en.wikipedia.org/wiki/Vandermonde_matrix) are "in general" in this case.

See this with an immediate recurrence.

"In general" because there is a certain number of subtle conditions on coefficients $a_k$ that have to be fullfilled (see the long remark by Aaron Meyerowitz).

Answer 5

The condition that any particular submatrix has determinant zero is a polynomial equation — the solution set has measure zero in the space of all matrices.

There are finitely many submatrices; the set for which some submatrix has determinant zero is is a finite union of measure zero sets, and thus has measure zero.

Consequently, almost all matrices are totally invertible.