3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – el_tenedor Dec 31 '15 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Zach Stone Dec 31 '15 at 22:57
  • $\begingroup$ 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)$? $\endgroup$ – el_tenedor Jan 1 '16 at 0:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Zach Stone Jan 1 '16 at 0:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$". $\endgroup$ – el_tenedor Dec 31 '15 at 21:50
  • $\begingroup$ @el_tenedor: I updated my answer. Hope it helps. $\endgroup$ – KittyL Dec 31 '15 at 22:01
  • $\begingroup$ +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). $\endgroup$ – el_tenedor Dec 31 '15 at 22:33
  • $\begingroup$ @el_tenedor: Sorry I am not sure if I understand what you meant. I updated my answer. $\endgroup$ – KittyL Dec 31 '15 at 23:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – el_tenedor Dec 31 '15 at 23:31
  • $\begingroup$ 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. $\endgroup$ – user59193 Dec 31 '15 at 23:36

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.