Maximizing the value of a determinant

Given the entries of a matrix how can we optimize its determinant?

So, if the entries of a $n\times n$ matrix belong to the set $\{a_1,a_2,\ldots ,a_p\}$, how to arrange them to maximize or minimize the determinant?

I have seen a result concerning $3 \times 3$ matrices,which says that determinant is maximum when all the diagonal elements are $\min\{a_i\}_{1\leq i\leq p}$ and all the off-diagonal elements are $\max\{a_i\}_{1\leq i\leq p}$. And once we maximize it, switching two rows or two columns we get the minimum value.

Also, i don't have any clue for higher order matrices. Any help would be appreciated. Thanks in advance.

Solution 1:

This problem contains http://mathworld.wolfram.com/HadamardsMaximumDeterminantProblem.html which is hard. This is an interesting 1-parameter extension (see below).

The number of matrices with entries drawn from $\{a_1, \ldots, a_p\}$ is finite, so the maximum is attained. Suppose $A$ is a matrix attaining it. I claim that every entry in $A$ is either $m=\min a_j$ or $M=\max a_j$. Indeed, viewed as a function of a single entry, the determinant is an affine linear function, so is maximized by making the entry maximal (if the slope is positive) or minimal (if the slope is negative). (Another way of saying the same thing is to take a row expansion; this shows that the slope is (up to sign) the complementary minor determinant).

Now we are just asking for the maximal determinant of a matrix with entries $m, M$.

The case $m=M$ is not interesting, so we can assume that one of them is non-zero and by rescaling reduce to the case of matrices with entries $1, r$. If $r=0$ or $r=-1$ we recover the "classical" cases.

Update: Yves Daoust is right that the determinant is divisible by $(x-1)^{(n-1)}$. We prove this in two ways:

1) By matrix determinant lemma,

$$\det\left(B + uv^T\right) = \det\left(B\right) + v^T\mathrm{adj}\left(B\right)u$$

applied to $u=v=[1, \ldots, 1]^T$ and $B=A-uv^T$, we get

$$\det A= \det B+ (\text{sum of entries of }\mathrm{adj}\left(B\right) ).$$

Since all the entries of $B$ are $0$ or $x-1$, so $\det B$ is a multiple of $(x-1)^n$, and all the entries of $\mathrm{adj}\left(B\right) )$ are multiples of $(x-1)^{(n-1)}$, the result follows.

2) Alternatively, we argue by induction using the Jacobi formula:

$$\frac{d}{dx} \det A(x) = \operatorname{tr} \left (\operatorname{adj}(A(x)) \, \frac{dA(x)}{dx}\right ).$$

Base case is empty (or we can take $n=2$ and check). Now for induction step we prove that $\frac{d}{dx} \det A(x)$ is divisible by $(x-1)^{(n-2)}$ and since $\det A(x)$ is divisible by $(x-1)$ it must be divisible by $(x-1)^{(n-1)}$. Indeed, $x=1$ is a root of $A(x)$, and its multiplicity is one more than the multiplicity of this root for $\frac{d}{dx} \det A(x)$.

Observe that $\operatorname{adj}(A(x))$ has entries minor determinants of $A(x)$, which are all matrices with entries $1$ and $x$ of size $n-1\times n-1$, so by induction hypothesis are divisible by $(x-1)^{(n-2)}$; the $\frac{dA(x)}{dx}$ is a matrix of 0s and 1s, so after multiplication we get a matrix every entry of which is divisible by $(x-1)^{(n-2)}$, hence so is its trace. We conclude by Jacobi formula that multiplicity of $x=1$ as a root of $\frac{d}{dx} \det A(x)$ is at least $n-2$, so its multiplicity as a root of $A(x)$ is at least $n-1$. QED.

In fact the quotient $\det A(x)/(x-1)^{(n-1)}$ is either constant or linear for degree reasons. If we knew what linear polynomial it could be, we would have a solution to the Hadamard's problem. In fact, in Hadamard problem for $\pm1$ matrices, we can multiply some rows by -1 and make a column of all 1s. Then (again for degree reasons) $\det A(x)/(x-1)^{(n-1)}$ is a constant. The Hadamard problem for $\pm1$ matrices is then equivalent to figuring out this constant; unfortunately that itself is equivalent to solving the corresponding problem for $0-1$ matrices, so it does not look like we are making any actual progress... For example, doing all this for Hadamard matrices we should get that the constant is $n^{n/2}/(-2)^{n-1}$.

Solution 2:

Conjectures:

In $d$ dimensional space, the points with coordinates taken from the set are contained in a hypercube between the limits $a_{\min}$ and $a_{\max}$. The determinant is proportional to the volume of the hyperpyramid formed by the origin and $d$ points from the network.

If I am right (but this needs to be confirmed), the largest volume is achieved by choosing corner points. Without loss of generality, we can take the values of $a_{\min},a_{\max}$ to be $1,x$ (irrespective of the order).

In the 2D case, the possible determinant are $x^2-1,x^2-x,x-1$ and $0$ (ignoring a global sign); after division by $x-1$, these are $x+1,x,1,0$.

In the 3D case, the choices are $x^3-3x+2,x^3-2x^2+x,x^3-x^2-x+1,\cdots$. After division by $(x-1)^2$, these are $x+2,x+1,x,\cdots$.

After a quick check, it seems that the values in 4D are $x+3,x+2,x+1,x,\cdots$ times $(x-1)^3$, which seems to confirm a simple pattern.

Update:

After seeing this information (Hadamard maximal determinant problem), it seems that a general solution is hopeless:

http://www.indiana.edu/~maxdet/