14
$\begingroup$

$A$ is a matrix sized $n\times n$, all elements in $A$ are $\pm1$. Find $\max |A|$.

My Attempt
Denote $f(n)=\max |A_{n\times n}|$.
$f(1)=1$.
$f(2)=2$ is also obviously.
If $n\ge2$, $|A|$ must be even.
For $n=3$, $f(3)\ge4$ because $\left|\begin{array} r1&1&1\\1&-1&1\\1&-1&-1 \end{array}\right|=4$. Also, $|A|=A_{11} A_{22} A_{33}+A_{12} A_{23} A_{31}+A_{13} A_{21} A_{32}-A_{13} A_{22} A_{31}-A_{11} A_{23} A_{32}-A_{12} A_{21} A_{33}$ can not be $6$ since $A_{11} A_{22} A_{33}A_{12} A_{23} A_{31}A_{13} A_{21} A_{32}A_{13} A_{22} A_{31}A_{11} A_{23} A_{32}A_{12} A_{21} A_{33}$ must be $1$. $1\ne 1\cdot1\cdot1\cdot(-1)\cdot(-1)\cdot(-1)$.
Hence we have $f(3)\ne 6$. $f(3)=4$.
For $n\ge4$, I have no idea where to start with $f(n)$.
A trivial bound is $0<f(n)\le n!$.
EDIT
Related question:Maximum value of Determinant of $3 \times 3$ Matrix with entries $\pm 1$
It is not duplicated since I am discussing $n\times n$ determinants, not $3\times3$.

$\endgroup$
  • 4
    $\begingroup$ $f(n) \leq n^{2}$ because any eigen value $\lambda$ is bounded by $n$ and $|A|$ is the product of the eigen values. $\endgroup$ – Kavi Rama Murthy Sep 10 '18 at 8:36
  • 1
    $\begingroup$ Related: oeis A003433 $\endgroup$ – Kemono Chen Sep 10 '18 at 9:01
  • 5
    $\begingroup$ This problem is called "Hadamard maximal determinant problem". $\endgroup$ – Kemono Chen Sep 10 '18 at 9:17
  • 3
    $\begingroup$ Your question seems to be an open problem... Anyway, consider adding the first column to each of the others. This does not change the determinant, but since $-1\equiv 1 \pmod 2$, each column $c_i$ can now be written as $2c_i'$ where $c_i'$ has integer entries. Thus $|A|=2^{n-1}|A'|$, where $|A'|$ is an integer. $\endgroup$ – Gabriel Romon Sep 10 '18 at 9:32
  • 2
    $\begingroup$ There's also a Hadamard bound for the determinant of a matrix. Look it up. $\endgroup$ – Gerry Myerson Sep 10 '18 at 10:21
6
$\begingroup$

From comments:

This is a semi-well-known open problem known as Hadamard's maximum determinant problem.

$\endgroup$

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.