5
$\begingroup$

If absolute values of all elements of $n \times n$ matrix A are less than 1, $|\det(A)| \leq n ^ {n/2}$

It's proved by induction by n. Base is obvious, and transition is the following: consider the $n \times n$ matrix A'. Let the elements from the first row be $a_0, ..., a_{n-1}$. Then $\det(A') = \Sigma_{i=0}^{n-1} (-1)^{i} a_i \det(A_i)$, where $A_i$ are the matrices obtained from $A'$ by deleting the $i$th column and the first row. $\forall A_i \det(A_i) \leq (n-1)^{(n-1)/2}$. So $\det(A') = \Sigma_{i=0}^{n-1} (-1)^{i} a_i \det(A_i) \leq \Sigma_{i=0}^{n-1} a_i (n-1)^{(n-1)/2} \leq n(n-1)^{(n-1)/2}.$ The last step is to prove that $\forall n \geq 2$ it's true that $n(n-1)^{(n-1)/2} \leq n^{n/2} $.

Here I am stuck. I've plotted it and it is true, but I have no idea how to prove it strictly. And maybe a more elegant solution exists? Induction is quite boring.

$\endgroup$
5
  • $\begingroup$ I think in order to complete the proof you have to show it exactly the other way around: $n(n-1)^{(n-1)/2}\leq n^{n/2}$, right? But interesting question. I would also be interested in what matrices achieve a maximal determinant here. $\endgroup$
    – M. Winter
    May 5, 2017 at 8:24
  • $\begingroup$ Vandermonde matrix. $\endgroup$
    – sooobus
    May 5, 2017 at 8:26
  • 2
    $\begingroup$ I think this statement is equivalent to the Hadamard inequality, and the wiki article contains a proof. $\endgroup$
    – M. Winter
    May 5, 2017 at 8:27
  • $\begingroup$ You mean a Vandermonde matrix achieves this bound if I plug in some arbitrary $\alpha_i<1$? Seems unlikely in general but I will check this. Maybe for some specific values. $\endgroup$
    – M. Winter
    May 5, 2017 at 8:31
  • 1
    $\begingroup$ If you plug in n roots of unity, it works (mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html) $\endgroup$
    – sooobus
    May 5, 2017 at 8:41

1 Answer 1

4
$\begingroup$

I think this works. Reformulate the problem geometrically. The problem is to show that if you have $n$ vectors $v_1,\cdots,v_n$ in $\mathbb{R}^n$, each of them constrained to lie in the hypercube $\{|x_i| \leq 1; 1 \leq i\leq n\}$, then the maximal length each $v_i$ can achieve is $\sqrt{n}$ (joining the origin to one of the vertices of the hypercube). Hence the absolute value of the volume of the parallelepiped that the $v_i$ determine is bounded above by the product of the maximal lengths $(\sqrt{n})^n$. This is what you wanted to prove. I leave it to others to figure out examples of $v_i$ which maximize the absolute volume, etc. It should be simple now. It helps to think geometrically sometimes (though in some cases, it is difficult to translate from Algebra into Geometry).

Edit 1: As M. Winter pointed out, it is essentially the Hadamard inequality, which I was implicitly using (I was just sure it had to be true, but did not know it carried Hadamard's name, so to speak).

Edit 2: Hadamard matrices, for the values of $n$ for which they exist, maximize the absolute value of the determinant, under the constraints that the absolute values of all elements are less than or equal to 1.

Edit 3: I just saw some comments of the OP, which indicates that she is working over $\mathbb{C}$. However, one can simply modify the proof to adapt it to the complex case. Over $\mathbb{C}$ the bound is sharp, but I don't think the bound is sharp in general over $\mathbb{R}$, simply because the orthogonal complement of the line joining the origin and a vertex of the hypercube might not contain "enough" vertices of the hypercube in general so as to form an orthogonal basis out of them (except in some special dimensions, which are the dimensions for which the Hadamard matrices exist).

Comment: I thank the OP for this question, because I was unaware of this nice problem!

$\endgroup$
3
  • $\begingroup$ Thanks for this answer. I like that your answer made reference to the volume of a parallelepiped. Can you think of a similar argument for putting a lower bound on the modulus of the determinant, provided it can be assumed to be non-zero? $\endgroup$
    – gen
    Aug 28, 2022 at 1:20
  • $\begingroup$ @gen, if you assume that the volume is nonzero, then a lower bound on the modulus of the determinant of $A$ is $s^n$, where $s$ is the smallest singular value of $A$ (which is positive). Let $G = A^T A$ be the Gram matrix of $A$. Choose a multiplicative matrix norm. Try to find a lower bound of $s$ in terms of $1$ divided by the norm of $G^{-1}$. It may or may not work, but this is an idea. $\endgroup$
    – Malkoun
    Aug 28, 2022 at 21:58
  • $\begingroup$ @gen, or possibly try to apply Hadamard's inequality to the inverse matrix? It is another idea. That being said, a lower bound question in this setup probably deserves another post (I currently don't have much time to think about it, but I am sure others are willing to help). $\endgroup$
    – Malkoun
    Aug 29, 2022 at 1:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .