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

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

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.

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)$

• Why do the authors even bother about $\det(A) \geq 0$? If you follow the proof that has been linked in my original post, they conclude $|\det(A)| \leq n^{n/2}$. Based on what you say, they should have concluded $\det(A) \leq n^{n/2}$. – el_tenedor Dec 31 '15 at 22:43
• There are two theorems here. One is the one a out optimizing Hadamard matrix determinants. It should be proved in the most possible generality. Then, there's the one about $A^T A$. That only uses a special case of he first theorem. – Zach Stone Dec 31 '15 at 22:57
• Which are the two theorems you mention? Regarding my post I found "Hadamard's Inequality" which seems to be the more general statement, and "Hadamard's (upper) bound" which is the inequality the above proof is seeking. As @forgetfulfunctor points out Hadamard's bound can be derived from Hadamards inequality. Still, I am confused about the absolute value. If the bound holds for $|\det(A)|$, it will also hold for $\det(A)$. Why do the authors not simply optimize $|\det(A)|$ instead of showing that it is valid to assume $\det(A) = \sqrt(B)$? – el_tenedor Jan 1 '16 at 0:31
• Finding a maximum for $|\det(A)|$ could potentially be very different from finding a maximum for $\det(A)$. Conveniently, they are the same, using the the 'multiply some row by $-1$' operation. That is the point the author is making (I'm pretty sure, anyway). The question of why do we care is pretty open. Perhaps it's just a cleanliness thing. Simplifying notation is helpful for legibility. Perhaps it will come up in a later proof where he sneaks some absolute value signs in at a critical moment. I do not know. – Zach Stone Jan 1 '16 at 0:44

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.

• Sorry, I have updated my post. You explained the part I already understood. I am still unsure how this leads to the conclusion, that "the maximum problem for $\det A$ is the same as for $\det B$". – el_tenedor Dec 31 '15 at 21:50
• @el_tenedor: I updated my answer. Hope it helps. – KittyL Dec 31 '15 at 22:01
• +1: Thanks. I had thought about this. Apparently, I am bad at posing questions. My concern was more about the implication (Multilinearity implies equivalent maximization of determinants) than about the individual statements itself (see Zach Stone's answer). – el_tenedor Dec 31 '15 at 22:33
• @el_tenedor: Sorry I am not sure if I understand what you meant. I updated my answer. – KittyL Dec 31 '15 at 23:01

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.

• Thanks for sharing. I knew this inequality, but it didn't occur to me that it could be used for the inequality my original post was referring to. Note that $\det$ is not antilinear, but multilinear (and alternating). – el_tenedor Dec 31 '15 at 23:31
• Whoops, yea I meant alternating. Also, you can see that you can reach the maximum bound when $n$ is a power of $2$, since you can just take $A_1=\left[\begin{smallmatrix} 1 & -1 \\ 1 & 1 \end{smallmatrix}\right]$, and keep forming blocks, $A_n=\left[\begin{smallmatrix} A & -A \\ A & A \end{smallmatrix}\right]$, I think. – user59193 Dec 31 '15 at 23:36