# Find maximal possible determinant value given constraint

Task is to find maximal possible determinant value for 2x2 and 3x3 matrices given following constraint: $$\sum_{i,j=1}^na_{ij}^2 \le 1$$
I was able to come up with solution, but I received the test result, where I scored zero for this task. I still hasn't got a chance to take a look at my examined paper, but for now I just want to find whether or not my solution was actually true.
Solution
First trivial idea is that optimum would be reached in the point of exact equality $\sum_{i,j=1}^na_{ij}^2 = 1$.
Then, terms which participate in det calculation with minus sign, must be negative or zero.
$$\left( \begin{matrix} \frac 1 {\sqrt 2} & 0 \\ 0 & \frac 1 {\sqrt 2} \end{matrix}\right)$$

$$\left( \begin{matrix} \frac 1 {\sqrt 3} & 0 & 0 \\ 0 & \frac 1 {\sqrt 3} & 0 \\ 0 & 0 & \frac 1 {\sqrt 3} \end{matrix}\right)$$
So, I came up with these matrices and respective det values are $\frac 1 2$ and $\frac 1 {3\sqrt 3}$.

Is that correct? Thanks!

-
It's probably something to do with the way you make the argument. I think the answer is correct but I got that through a geometric argument. Your argument that it must happen at exact equality is easily fixed, but I think you will have more difficulty fixing the argument that all the negative term should be 0. – Gina Jun 7 '14 at 9:15

Here is a geometric argument that I would give:

It is always possible to decompose any matrix into a product of an orthogonal matrix and an upper triangular matrix. Orthogonal transformation is isometry, so $\sum\limits_{i,j=1}^{n}a_{ij}^{2}$ is preserved on the upper triangular matrix. Orthogonal matrix have determinant 1 or -1, so no effects on absolute value of determinant. Hence we need to look only at determinant of upper triangular matrix with the same constraint, but determinant there are only affected by the diagonal.

-

I cannot follow your argument about minus sign. Instead I would reason as follows. The inequality given means the sum-of-squares of the column norms of the matrix should not exceed $1$. Clearly if it is actually less than$~1$ one and the determinant is positive, one can make the determinant bigger by scaling up some column, so this cannot happen in an optimal solution; we may therefore assume the sum-of-sqaures is equal to$~1$. (I'm implicitly using that their exists an optimal solution, which is because the determinant is a continuous function on the compact set of matrices satisfying the inequality.)

Now if two column norms are distinct, then one can similarly increase the determinant by scaling both columns, increasing the smaller one and decreasing the larger one while keeping their sum-of-squares constant. This is basically because the function $xy$ in the plane takes its maximum on any circle centred in the origin at its points where $x=y$; this is a simple calculation. Therefore one may henceforth assume that all columns have equal norms, which must be $\sqrt{\frac1n}$.

Finally argue that in the given cases, for the determinant to be maximal, all columns should be perpendicular to each other. If not, then one could add a multiple of one column to another (which leaves the determinant unchanged) so as to make the norm of the latter smaller; this again shows the solution is not optimal.

So the maximum determinant is obtained for mutually orthogonal columns all of norm-squared $\frac1n$, and the determinant for that case is $n^{-n/2}$; concretely $2^{-1}=\frac12$ for $n=2$ and $3^{-3/2}=\frac{\sqrt3}9$ for $n=3$. This value can be obtained for an appropriate diagonal matrix.

-

Given any $n \times n$ matrix $A =(a_{ij})$, we can view its columns as a collection of $n$ vectors $$\vec{v}_1, \vec{v}_2, \ldots, \vec{v}_n \in \mathbb{R}^n \quad\text{ with }\quad \vec{v}_j = (a_{1j}, a_{2j}, \ldots, a_{nj})\quad\text{ for } j = 1,\ldots n$$

The condition $$\sum\limits_{i=1}^n\sum\limits_{j=1}^n a_{ij}^2 \quad\text{ is equivalent to }\quad\sum_{j=1}^n |\vec{v}_j|^2 = 1.$$

The absolute value of $\det(A)$ is nothing but the volume of the hyper-parallelepiped span by the $n$ vectors $\vec{v}_j$. Fixing the magnitudes of $\vec{v}_j$, we know this volume is maximized when and only when the $\vec{v}_j$ are orthogonal to each other. i.e when the $\vec{v}_j$ span a hyper-cuboid.

In that case, we also know $$|\det(A)| = \prod_{j=1}^n|\vec{v}_j| = \sqrt{\prod_{j=1}^n|\vec{v}_j|^2} \underbrace{\le}_{\text{AM } \ge \text{ GM}} \sqrt{\left(\frac{1}{n}\sum_{j=1}^n |\vec{v}_j|^2\right)^n} = \frac{1}{\sqrt{n}^n}$$ The AM $\ge$ GM inequality in the middle becomes an equality when and only when all $\vec{v}_j$ has same norm. i.e when all $\displaystyle\;|\vec{v}_j| = \frac{1}{\sqrt{n}}\;$. The implications are:

1. The maximum value of $|\det(A)|$ subject to given constraint is $\displaystyle\;\frac{1}{\sqrt{n}^n}\;$ as what you know.
2. For those matrix $A$ which achieve the maximum value of determinant, the $n$ vectors $\displaystyle\;\sqrt{n}\,\vec{v}_1, \ldots \sqrt{n}\,\vec{v}_n\;$ are orthonormal. In other words, $\sqrt{n} A \in O(n)$ is a $n$-dim orthogonal matrix!

Conclusion

You have found the correct value of the maximum determinant but fails to describe the set of matrices which achieve this maximum determinant.

-

Let's consider case 1. Yes you are right it can't be greater than $1/2$. But I think you should have proved it in examine. Anyway, try to prove it using this. $$ab+cd\le \frac{1}{2}(a^2+b^2+c^2+d^2).$$

-

For a correct proof, you are missing the fact that the terms that participate in the calculation with negative sign may be negative as well. For the 2D case, what you want is essentially to maximize $ab-cd$ under the constraint $a^2+b^2+c^2+d^2 = 1$ (if it's less then one just multply all variables by a factor). I don't know if you know about optimization under constraints and the lagrange multiplier, which would be the obvious method here. I'll assume you don't have this and try to find a more elementary solution:

Lets have $c,d$ constant at first, then we are maximizing $ab$ under $a^2+b^2=1-c^2+d^2 = const$. But since $$0 \leq(a-b)^2 = a^2+b^2 -2ab = const - 2ab,$$ we know that $ab$ is maximal for $a=b$, since equality holds only there. In the same way, keep $a,b$ constant to maximize $-cd$. Here $$0\leq (c+d)^2 = c^2+d^2+2cd = const + 2 cd$$ which in the same way results in $c=-d$. Now we end up with maximize $a^2+c^2$ under $2a^2+2c^2 = 1$, which trivially has the value $1/2$, although your solution is not the only one, since for example $a=b=-c=d=1/2$ works as well.

The 3d case looks to complicated to do in this way, but maybe, we can solve it with a bit of linear algebra: We have

$$\sum_{i,j=1}^3 a_ij^2 = trace(A^T A)$$

which is the sum of eigenvalues of $A^TA$, while we maximize the product of eigenvalues $\det (A^T A) = \det(A)^2$ (doesn't matter if we maximize $\det(A)$ or $\det(A)^2$). So we maximize $\lambda_1\lambda_2\lambda_3$ under $\lambda_1+\lambda_2+\lambda_3 = 1$. By similiar arguments as above we find that $\lambda_1=\lambda_2=\lambda_3=1/3$ is the solution. So we just need a matching $A$ such that $A^TA$ has those eigenvalues, which in fact is the case for your solution. This actually works in any dimension.

-

It's not obvious to me that it would be impossible to make the determinant larger in some way by having larger terms subtracted, if this caused larger terms to be added at the same time. Can you clarify why you think the terms participating with a minus sign would need to be zero or negative?

Edit:

Let the columns be denoted by $u, v, w$.

I agree about the maximum being attained on the surface where $|u|^2 + |v|^2 + |w|^2 = 1$.

The differential of $\det(u,v,w)$ is $(h,k,l) \mapsto \det(h,v,w) + \det(u,k,w) + \det(u,v,l) = (v \times w) \cdot h + (w \times u) \cdot k + (u \times v) \cdot l$.

The differential of $|u|^2 + |v|^2 + |w|^2$ is $(h,k,l) \mapsto 2u \cdot h + 2v \cdot k + 2w \cdot l$.

The Lagrange multiplier method implies that at a point that optimizes the determinant, these linear functionals need to be proportional. So the triple of vectors $(u,v,w)$ needs to be proportional to $(v \times w, w \times u, u\times v)$. This proves that $u$, $v$ and $w$ all need to be orthogonal, and after an (orthogonal) change of basis, you can assume your matrix is diagonal. From there I reach the same result as you.

-
That must have been comment, not an answer, I suppose. What I meant is in order to maximize determinant, minors with negative sign in front of them, must be negative or zero. – wf34 Jun 7 '14 at 9:08
I don't have the right number of points to comment. Yes, I'm asking you to clarify why you think that would be the case. – user155747 Jun 7 '14 at 9:16
I like Gina's proof. – user155747 Jun 7 '14 at 9:29
Change of basis does not leave the value $\sum_{i,j}a_{i,j}^2$ invariant, in general. – Marc van Leeuwen Jun 7 '14 at 9:50
I should have said orthogonal change of basis – user155747 Jun 7 '14 at 9:51