Maximize $\det (A)$ subject to $\|A\|_{\text{F}} \le 1$

Question

$A$ is an $n \times n$ matrix such that the sum of squares of its elements is less than or equal to 1.

What is $\max \det (A)$?

(a) $n = 2$

(b) $n = 3$

My partial solution

For $n = 2$, I think the answer is 0.5. Define the constrained maximisation problem as $$\max(a_{11}a_{22}-a_{21}a_{12})$$ such that $$a_{11}^2+a_{12}^2+a_{21}^2+a_{22}^2 \le 1$$ If $a_{21}=a_{12}=0$, the maximum $0.5$ is achieved at $a_{11}=a_{22}=1/\sqrt{2}$.

If $a_{21} \ne 0, a_{12}\ne0$, the maximum $0.5$ is achieved at $a_{11}=a_{22}=a_{21}=0.5$ and $a_{12}=-0.5$

But how to I prove that formally? And how to I tackle the more difficult case of $n=3$?

Answer 1

Let $v_1, \ldots, v_n$ be the column vectors of $A$. By Hadamard's inequality, we have $$\det(A) = \prod_{i=1}^n \|v_i\|$$ We are told the sum of squares of $A$'s elements $\le 1$. In terms of $v_i$, this means $$\sum_{i=1}^n \|v_i\|^2 = 1$$ By GM $\le$ AM, we have

$$\left(\prod_{i=1}^n \|v_i\|^2\right)^{1/n} \le \frac1n \sum_{i=1}^n \|v_i\|^2 = \frac1n \quad\implies\quad\det(A) \le \frac{1}{n^{n/2}}$$ Notice when $A = \frac{1}{\sqrt{n}} I_n$, the equality on RHS is achieved. This means above inequality is an optimal one.

Update

People seem to be interested in an explicit proof for the $n = 3$ case.
For completeness, here is a proof of Hadamard's inequality at $n = 3$.
Notice

1. For $3 \times 3$ matrix $A$ with columns $v_1,v_2,v_3$; we have $\det A = v_1 \cdot (v_2 \times v_3)$.
2. For any $u, v \in \mathbb{R}^3$, we have the vector identity $|u|^2 |v|^2 = (u\cdot v)^2 + |u \times v|^2$.

We find $$\begin{align}|\det A|^2 &= |v_1 \cdot (v_2 \times v_3)|^2 = |v_1|^2|v_2 \times v_3|^2 - |v_1 \times (v_2 \times v_3)|^2\\ &= |v_1|^2|v_2|^2|v_3|^2 - ( |v_1|^2 (v_2 \cdot v_3)^2 + |v_1 \times (v_2 \times v_3)|^2)\\ &\le |v_1|^2|v_2|^2|v_3|^2 \end{align} $$

Answer 2

For $n=2$, you can use the inequality $a_{11} a_{22} \le 0.5(a_{11}^2+a_{22}^2)$ and the same for $a_{21}$, $a_{12}$ to see that

$$a_{11}a_{22}-a_{21}a_{12} \le \frac{a_{11}^2+a_{22}^2+a_{12}^2+a_{21}^2}{2} = \frac 12$$.

For the case $n=3$ look here: Update: no, it was not a good idea.

Answer 3

Maybe one should look at $\det (A)$ as a volume of cube spanned by its rows. Then $\det (A)$ is maximal when the rows are perpendicular, and in this case $\det (A)$ is the product of the lengths of the rows. So, the problem reduces to the classical inequality between arithmetical and geometrical means.

Answer 4

Interestingly, maximizing the logarithm of the determinant is a convex optimization problem.

$$\begin{array}{ll} \text{maximize} & \log \det( \mathrm A)\\ \text{subject to} & \| \mathrm A \|_{\text{F}}\leq 1\end{array}$$

Using CVXPY to solve the convex program numerically for $n \in \{2,3,\dots,9\}$:

from cvxpy import *
import numpy as np

for n in range(2,10):

    print "\n\nn = ", n, "\n"

    A  = Variable(n,n)

    # create convex optimization problem
    prob = Problem( Maximize(log_det(A)),
                    [norm(A,'fro') <= 1] )

    # solve optimization problem
    prob.solve()

    # print rounding of optimal matrix A 
    print np.round(A.value, 3)

which produces the following output:

n =  2 

[[ 0.706 -0.   ]
 [-0.     0.706]]


n =  3 

[[ 0.576 -0.     0.   ]
 [-0.     0.576 -0.   ]
 [ 0.    -0.     0.576]]


n =  4 

[[ 0.499 -0.    -0.    -0.   ]
 [-0.     0.499 -0.     0.   ]
 [ 0.    -0.     0.499  0.   ]
 [-0.     0.    -0.     0.499]]


n =  5 

[[ 0.447  0.     0.    -0.    -0.   ]
 [-0.     0.447 -0.     0.     0.   ]
 [ 0.     0.     0.447  0.     0.   ]
 [-0.     0.    -0.     0.447 -0.   ]
 [ 0.     0.     0.    -0.     0.447]]


n =  6 

[[ 0.407 -0.    -0.     0.     0.    -0.   ]
 [-0.     0.407  0.    -0.    -0.     0.   ]
 [-0.     0.     0.407  0.     0.     0.   ]
 [ 0.    -0.    -0.     0.407 -0.    -0.   ]
 [ 0.    -0.     0.    -0.     0.407 -0.   ]
 [ 0.     0.     0.    -0.    -0.     0.407]]


n =  7 

[[ 0.377 -0.     0.     0.     0.    -0.    -0.   ]
 [ 0.     0.377  0.     0.    -0.    -0.    -0.   ]
 [-0.    -0.     0.377  0.     0.    -0.     0.   ]
 [ 0.     0.    -0.     0.377 -0.    -0.    -0.   ]
 [ 0.    -0.    -0.     0.     0.377 -0.     0.   ]
 [-0.     0.    -0.    -0.    -0.     0.377  0.   ]
 [-0.     0.     0.    -0.     0.     0.     0.377]]


n =  8 

[[ 0.353 -0.    -0.     0.     0.     0.    -0.    -0.   ]
 [ 0.     0.353  0.     0.     0.    -0.     0.    -0.   ]
 [ 0.     0.     0.353 -0.     0.    -0.    -0.    -0.   ]
 [-0.    -0.    -0.     0.353 -0.     0.     0.     0.   ]
 [-0.    -0.     0.    -0.     0.353 -0.     0.     0.   ]
 [ 0.    -0.    -0.    -0.    -0.     0.353 -0.    -0.   ]
 [ 0.     0.    -0.    -0.     0.    -0.     0.353  0.   ]
 [-0.    -0.    -0.     0.     0.    -0.    -0.     0.353]]


n =  9 

[[ 0.333  0.    -0.     0.     0.    -0.    -0.    -0.     0.   ]
 [ 0.     0.333 -0.     0.    -0.    -0.    -0.     0.    -0.   ]
 [-0.    -0.     0.333 -0.    -0.     0.     0.    -0.     0.   ]
 [ 0.    -0.    -0.     0.333 -0.    -0.    -0.    -0.     0.   ]
 [ 0.    -0.    -0.    -0.     0.333 -0.    -0.     0.    -0.   ]
 [ 0.    -0.     0.    -0.     0.     0.333  0.     0.    -0.   ]
 [-0.    -0.     0.    -0.    -0.    -0.     0.333 -0.     0.   ]
 [-0.     0.    -0.    -0.     0.    -0.    -0.     0.333 -0.   ]
 [-0.    -0.     0.    -0.    -0.     0.     0.    -0.     0.333]]

which suggests that the optimal solution is indeed

$$\mathrm A = \frac{1}{\sqrt{n}} \mathrm I_n$$

as stated by achille.