Is there a sequence of matrices $(A\_n\in M\_{2^n\times2^n}(\mathbb{Z}))\_{n\in\mathbb{N}}$ such that the $(i,j)$th entry of $A\_n$ is computable in polynomial time, such that all minors of each $A\_n$ are nonzero?


The last condition is easy to satisfy without the entries being computable in polynomial time, by using Vandermonde matrices. But the entries of a $2^n\times2^n$ Vandermonde matrix are too large to write down in polynomial time (since a row of powers of $k$ will end with $k^{2^n-1}$, which takes $(2^n-1)\log(k)>poly(n)$ digits to write down).


I'm also interested in the same question where rational, rather than just integer, entries are allowed.



Are there large integer matrices with entries computable in polynomial time, such that all minors are nonzero?
For rational entries, a [Cauchy matrix](https://en.wikipedia.org/wiki/Cauchy_matrix) works, e.g. $a\_{ij} = 1/(2^n+i-j)$.


For integer matrices, pick a prime $p > 2^{n+1}$, and let $a\_{ij}$ be the smallest positive residue of $1/(2^n+i-j) \bmod p$, which can be computed in polynomial time by the extended Euclidean algorithm. By the formula for a Cauchy determinant, all minors are nonzero modulo $p$, so they remain nonzero as integers.


