How to minimize a determinant, without a computer?

Question

I was asked to find the minimum value of a determinant of order $3\times 3$ having elements $-1$ and $1$, and after trial and error, was able to come up with this $$ \begin{vmatrix} -1 & 1 & -1 \\ 1& 1 & 1 \\ -1 & - 1& 1 \\ \end{vmatrix} = -4$$

However, this seems like a brutalist approach, and was looking for simpler methods.

I have come across answers like this on maximizing and minimising a 3 by 3 matrix, however, as this is for school, I can't use computers for more complicated problems

Answer 1

You can solve this without actually computing any determinants. The three rows correspond to three points; the determinant is (up to sign) 6 times the volume of the tetrahedron whose corners are your three points together with the origin. You can always change the sign if you need to by swapping two rows.

Given that the coordinates are all $\pm1$, you can choose from eight possible points, which form the corners of a cube whose side lengths are all $2$. If you want the determinant to be nonzero, you have to pick three corners such that none is directly opposite any of the others (equivalently no row can be the negative of any other row.) (In this simple problem it turns out that’s all you have to worry about.)

Rotating the cube preserves volume, so you can pick the first row (point on the cube) however you like. The second point can’t be opposite the first, so it must share a face with the first point, either adjacent or directly opposite. By symmetry, each of the three pairs must share a face.

One way to accomplish this is if the three points are the vertices of a triangle on a single face of the cube, for example $(1,1,1)$, $(1,1,-1)$, and $(1,-1,-1)$, The area of the triangle is $2$ (half the area of the face) so the tetrahedron has volume $2/3$ (recall $V= 1/3 bh$) and the determinant is $\pm4$. (The sign depends on whether you list the points clockwise or counterclockwise.)

But any other solution can be turned into this one. To see this, fix a face, and take any points of your triple that aren’t in the face and reflect them through the origin to put them in the face; this might change the sign of the determinant but not the absolute value. The three points are now in one face and must be distinct, so we’re in the case already analyzed. Thus the only possible nonzero determinants are $4$ and $-4$.

Answer 2

Let $S = \{-1,1\}$. Given any matrix $M$ with all of its elements in $S$, let $v_1, v_2, v_3 \in S^3$ be its column vectors.

We thus have it such that

$$\det (M) = \det[ v_1, v_2, v_3 ] = 4 \det\left[ v_1, \frac{v_1+v_2}{2}, \frac{v_1+v_3}{2} \right]$$

for some $\frac{v_1+v_2}{2}, \frac{v_1+v_3}{2} \in \mathbb{Z}^3$. This follows from the fact that in a $n\times n$ matrix, adding a column to another column does not change the determinant. We will factor out a $\frac12$ from both the second and third column after adding the first column to them.

Since the sum $(\pm1)+(\pm1)$ is always even, we can divide by 2 safely and guarantee that the remaining column is still consists of integers.

Hence, $\det (M) = 4n$ for some $n \in \mathbb{Z}$. The determinant of $M$ is the sum of $6$ terms, all with values $\pm 1$. Thus, $|\det (M)| \le 6$.

There are only $3$ valid values the determinant in question can take on given all of these restrictions, namely, $0$ and $\pm 4$.

Thus the minimum determinant must be $-4$, with one possible matrix being $$M=\begin{bmatrix} -1 & 1 & -1 \\ 1 & 1 & 1 \\ -1 & - 1& 1 \\ \end{bmatrix}$$ just as you've noted.

Answer 3

A different approach to finding the minimum of $-4$, based on the combinatorically based definition of the determinant.

Call the matrix $A$ and it's elements $a_{ij}$. Then of course we have

$\det(A)=a_{11}a_{22}a_{33}+a_{12}a_{23}a_{31}+a_{13}a_{21}a_{32}-a_{11}a_{23}a_{32}-a_{12}a_{21}a_{33}-a_{13}a_{22}a_{31}$

In a perfect world we could "optimize" the products so that all the terms have the right signs to contribute $-1$ to the determinant, to wit:

$a_{11}a_{22}a_{33}=a_{12}a_{23}a_{31}=a_{13}a_{21}a_{32}=-1$

$a_{11}a_{23}a_{32}=a_{12}a_{21}a_{33}=a_{13}a_{22}a_{31}=+1$

$\det(A)=-6$

But we live in an imperfect world ... .

Reality (and parity) check

Alas, we cannot do this because the product of all nine entries is rendered as

$(a_{11}a_{22}a_{33})(a_{12}a_{23}a_{31})(a_{13}a_{21}a_{32})$

and also

$(a_{11}a_{23}a_{32})(a_{12}a_{21}a_{33})(a_{13}a_{22}a_{31})$

but the optimal assignments we proposed above give $-1$ for the first product versus $+1$ for the second! To make the products agree we need an even number of the individual permutations to give a $-1$ product. When we put this constraint into the determinant formula we get, as identified elsewhere, a forced multiple of $4$. So the lowest possible determinant, assuming there can be nonzero determinants at all, must be $-4$ not $-6$.

The (or a) correct solution

We modify our terms to meet the parity requirement:

$a_{11}a_{22}a_{33}=a_{12}a_{23}a_{31}=a_{13}a_{21}a_{32}=a_{12}a_{21}a_{33}=-1$

$a_{11}a_{23}a_{32}=a_{13}a_{22}a_{31}=+1$

$\det(A)=-4$

We check by setting out to construct the matrix explicitly. We know from the parity check that only five permutation products are independent, so we begin by specifying four entries

\begin{pmatrix} 1&1&1\\1&*&*\\*&*&*\\\end{pmatrix}

Then the product $a_{12}a_{21}a_{33}=-1$ forces the lower right element to $-1$, then the product $a_{11}a_{22}a_{33}=-1$ makes the center element $+1$, and so on; we find that the matrix below satisfies all the corrected product relations above and indeed has a determinant of $-4$:

\begin{pmatrix} 1&1&1\\1&1&-1\\1&-1&-1\\\end{pmatrix}

Out of $512$ total $3×3$ matrices we might construct with elements of $\pm1$, $96$ each have determinants of $+4$ and $-4$. The rest have determinant $0$.