The Hadamard inequality roughly says that the determinant of an $n \times n$ matrix whose entries are real numbers with absolute value at most $1$ is not greater than $n^{n/2}$. Can you find arbitrarily large matrices with entries of absolute value at most $1$ for which the equality holds (ie the determinant is exactly $n^{n/2}$)? You don't have to find such an $n \times n$ matrix for each $n$ (for some $n$'s this may be impossible, while for others this is a very difficult, unsolved problem), just find a family for arbitrarily large $n$. Can you also give a quick proof of the inequality? Note: the inequality also holds for complex-valued matrices, but you don't have to use complex numbers to solve this problem.
Bonus problem: is it possible to have equality if the matrix is a real $3 \times 3$ matrix?
Update (09/03/2008): Solution posted! (show solution)
The inequality can be quickly proved if you note that the Euclidean norm of a column vector is at most $\sqrt{n}$, and that the determinant is also the volume of the parallelepiped defined by the column vectors. Since its volume in the lucky case that the column vectors are all orthogonal is exactly $\sqrt{n}^n$, we have the estimate (alternatively you can note that applying Gram-Schmidt orthogonalization the norm of the vectors is not increased and the determinant stays the same, so you end up with orthogonal vectors that are smaller or of equal size, and you can estimate here the determinant).
Now, the problem asks if we can show arbitrarily big matrices where the equality holds, and we can do this by finding $n$ orthogonal vectors with coordinates $-1$ o $1$, and this can be done inductively: if we have found such $n$ vectors with $n$ components, we will show $2n$ new vectors with $2n$ components. Suppose that we have $v_i = (a_{i1},..., a_{in})$, our new vectors will be $w_i = (a_{i1},..., a_{in}, a_{i1},..., a_{in})$ for $i = 1,...,n$ and $w_i = (a_{(i-n)1},..., a_{(i-n)n}, -a_{(i-n)1},..., -a_{(i-n)n})$ for $i = n+1,...,2n$. It is straightward to see that the $w_i$ are orthogonal (because the $v_i$ are), and they have the maximum allowed norm, so we have our good matrix because the inductive step is trivial (just take the constant $1$). What we did is passing from the matrix $M$ to the double-sized matrix $N$ containing $M$ in all corners except for the down-right corner that contains $-M$ instead.
Note: we found such matrices for all the powers of $2$. It was proved that the equality cannot hold if $n$ is not $1$, $2$, or $4k$ for some $k$, and it is an open problem (Hadamard conjecture) to prove if it can be done for all $n = 4k$.
Solution of the bonus problem: the vectors that are in such an hypothetical matrix must have norm exactly $\sqrt{n}$, so they must lie on the sphere with radius $\sqrt{n}$. But the condition of having entires at most $1$ forces them to be in the 3-dimensional cube $[-1,1]\times[-1,1]\times[-1,1]$. Thus the only possibilities are the vertices of the cube, and you cannot find $3$ of them that are orthogonal.
No comments:
Post a Comment