The Hadamard determinant problem: understanding a proof for the upper bound on matrix determinants

Question

I'm working through a proof on The Hadamard determinant problem which can be found in

Proofs from THE BOOK.

I don't understand how the transition from real valued matrices $A$ with entries in $\{-1,1\}$ to matrices $B = A^T A$ is justified. Of course, in the end we want to use the spectral theorem for symmetric matrices. Furthermore, $|\det A| = \sqrt{\det B}$.

But this is what the authors are writing, and I am not fully understanding:

Since multiplication of a column of $A$ by $-1$ turns $\det A$ into $-\det A$, we see that the maximum problem for $\det A$ is the same as for $\det B$.

Maybe someone unterstands the role of the multilinearity of $\det$ in this argument and can share some insight. The conclusion, which is represented in bold letters, is the part which is bothering me.

Answer 1

The point is to use that $|det(A)| =\sqrt{det(B)}$, so by (maybe) changing the sign of one row of $A$, we can assume $det(A) \geq 0$. Here you need to use the fact that after changing the sign of one row of$A$ leaves us with a different matrix, but one that still satisfies the assumption of having only $-1/1$ entries. So we have the problem of optimizing $\sqrt{det(B)}$. But this is the same as optimizing $det(B)$

Answer 2

Remember the $j$-th column expansion formula for determinant of $A$:

$$\sum^n_{i=1}(-1)^{i+j}a_{ij}det(A_{ij})$$

where $A_{ij}$ is the matrix obtained by deleting the $i$-row and $j$-th column of $A$.

Using this formula, you can see that when you multiply the whole $j$-th column by $-1$, all the $a_{ij}$'s turn to $-a_{ij}$. This makes the determinant of $A$ negative of the original.

Edit:

Since $\det(A^TA)=\det(B)$, so $\det(B)=\det(A)^2$. Hence $|\det(A)|=\sqrt{\det(B)}$. If $y=\sqrt{x}$, then finding the maximum of $y$ is of course equivalent as finding the maximum of $x$, since the function $\sqrt{x}$ is monotonically increasing.

Edit 2:

Sorry I am not sure if I understand your question. The multilinearity guarantees that the maximum happens at the boundaries, which are $-1, 1$. They don't imply the statement about $\det{B}$. Think about a linear function $z=ax+by$, where $x,y$ are bounded above and below. Then the maximum would happen at the boundaries. Here you treat the determinant as a linear function in terms of the $a_{ij}$'s.

Answer 3

If you don't mind, I have a slightly different way of deriving the Hadamard bound that you seek, which I find particularly enlightening.

Step 1: observe that for $v_1,v_2,\ldots,v_n\in\mathbb{R}^n$, the volume of the parallelepiped spanned by these vectors is $\det [v_1\ v_2\ \ldots\ v_n]$, i.e. the determinant of the matrix with the $v_i$ as columns; this is a geometric insight into the alternating-ness of $\det$, as you were seeking. You can prove this step by an analytic geometry argument.

Step 2: observe that the volume of a parallelepiped is always at most $|v_1|\cdot |v_2|\cdot\ldots\cdot |v_n|$, with equality iff the parallelepiped is a box, i.e. if the $v_i$ are orthogonal. Already, this gives us Hadamard's inequality! $\det [a_{ij}] \le \prod_{j=1}^n \sqrt{\sum_{i=1}^n a_{ij}^2}$.

Step 3: if all $|a_{ij}|\le M$, then by the above inequality, $\det [a_{ij}]\le M^n n^{n/2}$. Plug in $M=1$ and this is the result you seek.