5
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Doesn't the log apply to both power and base for how long exponentiation takes? $\endgroup$
    – user44191
    Commented Feb 6, 2019 at 23:29
  • $\begingroup$ You can't write down an $n$-digit number in less than $n$ steps, and the power contributes linearly to log, which is the number of digits long the number is. $\endgroup$
    – Alex Mennen
    Commented Feb 6, 2019 at 23:42

2 Answers 2

Reset to default
16
$\begingroup$

For rational entries, a 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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I suppose that finding $p$ in polynomial time is still conjectural; e.g. test $2^{n+1}+k$ for primality for $k=1,3,5,\ldots$ until the first prime appears: each test is poly($n$) time ("PRIMES is in P"), and we expect but cannot prove that so is the minimal $k$. $\endgroup$
    – Noam D. Elkies
    Commented Feb 7, 2019 at 3:33
  • 1
    $\begingroup$ If we allow the algorithm some randomness, one can provably find a prime in (probabilistic) polynomial time. See "second argument" here michaelnielsen.org/polymath1/… $\endgroup$
    – usul
    Commented Feb 7, 2019 at 14:07
2
$\begingroup$

A $2^n \times 2^n$ Hadamard matrix, see https://en.wikipedia.org/wiki/Hadamard_matrix, has entries $\pm 1$ and is equal to its transposed inverse (up to a scalar factor $2^n$). Thus all its minors are nonzero.

The Wikipedia article contains Sylvester's contruction of a $2^n \times 2^n$ Hadamard matrix. With the information in that article it is easy to see that an entry of such a matrix can be computed in time $O(n)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Counterexample: the $(1,2) \times (1,2)$ minor in the Hadamard matrix $$\begin{array}{c}+\,+\,+\,+\cr+\,+\,-\,-\cr+\,-\,+\,-\cr+\,-\,-\,+\end{array}.$$ (That happens to be a symmetric minor, but note that asymmetric ones must also be nonzero; here $(1,2) \times (3,4)$ gives zero.) $\endgroup$
    – Noam D. Elkies
    Commented Feb 8, 2019 at 14:50
  • $\begingroup$ I was looking at the $(2^n-1) \times (2^n-1)$ minors only. If you also consider smaller minors, you are right, of course. $\endgroup$
    – Martin Seysen
    Commented Feb 8, 2019 at 16:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .