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

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.


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.)


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.