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
    Feb 6 '19 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
    Feb 6 '19 at 23:42
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
    Feb 7 '19 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
    Feb 7 '19 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
    Feb 8 '19 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
    Feb 8 '19 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.