Let $p$ be a large prime number. I want a $k\times k$ matrix with determinant $p$ and bounded integer elements (say, from -100 to 100). For which minimal $k$ such a matrix does always exist? We can not hope for anything better than $k=O(\log p/\log\log p)$, which corresponds to $p\sim k^{Ck}$, and we may always achieve $k=O(\log p)$ if I understood correctly the answers to this question (determinant of (0,1) $k\times k$ matrices achieve all values between 0 and something exponential in $k$.)

  • 2
    $\begingroup$ Alternatively, the bound $k = O(\log p)$ can be achieved by writing $p=Q(2)$ where $Q$ is a polynomial with coefficients in $\{ 0 ,1 \}$ (base $2$ expansion), and then by noting that $p = \det(2 I - M)$ where $M$ is the companion matrix of $Q$. The matrix $ 2I - M$ has coefficients in $\{-1,0,1,2,3 \}$. $\endgroup$ – js21 Feb 6 '17 at 14:32
  • $\begingroup$ Yes, but such constructions can not give better bounds, since after an elementary transform the rows of our matrix (almost all of them) have bounded norms. $\endgroup$ – Fedor Petrov Feb 6 '17 at 19:12
  • 1
    $\begingroup$ So, you need something better than just saying it's between $\log p$ and $\log p/\log\log p$? $\endgroup$ – Gerry Myerson Feb 6 '17 at 22:10
  • $\begingroup$ I think he wants a proof that it is O(log p/ log log p). I don't have a proof, but a darned good idea (augmentation) in that direction. Gerhard "It's The Idea That Counts" Paseman, 2017.02.06. $\endgroup$ – Gerhard Paseman Feb 6 '17 at 22:51
  • 1
    $\begingroup$ @GerryMyerson Yes, I am not completely satisfied by this double logarithm gap between lower and upper bound. $\endgroup$ – Fedor Petrov Feb 7 '17 at 13:46

No answer, but an observation and a suggestion.

As p is a prime, the Smith Normal Form of such a matrix will have all entries equal to 1, save for the last. This means the matrix will need to have small (determinants for some of its) minors and that (by truncating to lower dimensions) the span of some rows will have a small volumed facet. It may be possible to set k to that value so that $(Mk^{1/2})^k$ is a little larger than p (and $M$ plays the role of 100) and then use random matrices with large and sufficiently coprime entries, but it might be better to try to reverse engineer a SNF matrix to build what you want.

Another approach is augmentation. Start with an order n matrix Q with large determinant near p in size. The determinant will likely have few or no prime factors larger than log(p). Build an order n+1 matrix with Q as minor, and play with the additional row and column to get the determinant closer to p. If Q resembles a Hadamard matrix, the determinant of the augmented matrix will share many prime factors in common because the minors of Q will be mostly the same. Call this attempt P.

Now the minors of P will have more variation, and you can augment P to get a determinant even closer to p. My intuition suggests that fewer than log n augmentations will be needed to reach p. If you decide to try it, I suggest playing with Mersenne and Proth primes with b binary digits, M something less than b, and start with n about square root of b or smaller.

MathOverflow has references of which I remember only fragments. Richard Stanley has recently been coauthor on a paper involving SNF of such matrices, and there have been questions asking about determinant spectra for matrices with small entries. I recommend you ask Will Orrick directly if he does not respond to this post.

Gerhard "Hasn't Improved On Exponential Lately" Paseman, 2017.02.06.


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.