Maximum value of determinant of a matrix P

Question

If P is 3×3 matrix and all the entries in P are from set {-1,0,1}. Then the find the maximum possible value of determinant P. I got the answer which is 4 using hit and trial method. But i need some specific methodology to solve this problem.

Answer 1

Let $P = (p_{ij})$ be any $3 \times 3$ matrix with entries from $\{ 0, \pm 1 \}$.

When one expand $\det P$ out completely, it becomes a combination of $6$ numbers $A, B, C, D, E, F$ from $\{ 0, \pm 1 \}$.

$$\det P = A + B + C - D - E - F \tag{*1}$$

The first consequence of this is $|\det P| \le 6$.

However, $|\det P|$ cannot equal to $5$ nor $6$. This is because the $6$ numbers satisfy another relation $$ABC = DEF = \prod_{i=1}^3\prod_{j=1}^3 p_{ij}\tag{*1}$$

• If $\det P = 6$, then $(*1)$ demands $A = B = C = -D = -E = -F = 1$.
  However, $ABC = 1 \ne -1 = DEF$, violating $(*2)$.

• If $\det P = 5$, then one and only one of $A, B, C, D, E, F$ need to be zero.
  This leads to $ABC \ne DEF$ again.

• If $\det P = -6$ or $-5$, them $\det(-P) = 6$ or $5$, contradict with what we have just proved.

Combine these, we can conclude $|\det P| \le 4$.

Since this value $4$ is achieved by matrix $\begin{bmatrix} +1 & +1 & +1\\ -1 & -1 & +1\\ +1 & -1 & +1 \end{bmatrix}$, the maximum value of $\det P$ is $4$.

Answer 2

$P= (p_1, p_2, p_3)$ can be thought as made up by three vectors $p_i \in \{-1, 0, 1\}^3$.

You can picture all feasible vectors starting at the origin $(0,0,0)$ pointing to one of the $3\times 3\times 3$ feasible points within the cube $[-1,1]^3$.

As $$ V = \lvert \det(p_1, p_2, p_3) \rvert = \lvert p_1 \cdot (p_2 \times p_3) \rvert = \lVert p_1 \rVert \lVert p_2 \rVert \lVert p_3 \rVert \lvert \cos \alpha \rvert \lvert \sin \beta \rvert $$ is the volume of the parallelepiped spanned by the $p_i$ you want linear independent vectors which are as long as possible while being as far apart as possible.

So it makes more sense to pick diagonals of the cube, than the orthogonal sides.

Answer 3

The "methodology" may be as follows. We search better for maximum absolute value, same problem. Then we consider such a $P$, realizing the maximum absolute value.

Let $c$ be the column / row of $P$ having the maximal number of non-zero entries. After possible transposition, and movement of this column/row to the first place, and multiplication of all $-1$ first column entries with $-1$ in the corresponding row, we can assume $P$ to be of one of the shapes: $$ \begin{bmatrix} 1 & * & *\\ 1 & * & *\\ 1 & * & * \end{bmatrix} \ ,\qquad \begin{bmatrix} 1 & * & *\\ 1 & * & *\\ 0 & * & * \end{bmatrix} \ ,\qquad \begin{bmatrix} 1 & * & *\\ 0 & * & *\\ 0 & * & * \end{bmatrix} \ . $$ In the last case, we have at most one non-zero entry in each row/column, so we can realize only a determinant $0,\pm 1$, we can forget about it. (Soon we see bigger values.)

In the first case, we have three rows, that we can permute arbitrarily, and the entries in these rows can be only $1,0,0$, and $1,0,1$, and $1,1,0$, and $1,1,1$, so after exchanging the star-columns, we can assume the row $1,1,0$ is present (or the determinant is zero, two repeating rows).

In the second case, the last row cannot be zero. So it has an entry equal to $1$, we move it in the second column. We have thus to consider only the shapes, that may realize the maximum (absolute value): $$ \begin{bmatrix} 1 & 1 & 0\\ 1 & * & *\\ 1 & * & * \end{bmatrix} \ ,\qquad \begin{bmatrix} 1 & * & *\\ 1 & * & *\\ 0 & 1 & * \end{bmatrix} \ . $$ In both cases, we perform linear operations on rows/columns to get an isolated $1$ at position $(1,1)$ in its row/column, so that the determinant can be easily computed: $$ \begin{bmatrix} 1 & 0 & 0\\ 1 & *-1 & *\\ 1 & *-1 & * \end{bmatrix} \ ,\qquad \begin{bmatrix} 1 & * & *\\ 0 & *-* & *-*\\ 0 & 1 & * \end{bmatrix} \ . $$ There are now fewer cases to be studied, the cases are: $$ \begin{bmatrix} *(-2,-1,0) & *(-1,0,1)\\ *(-2,-1,0) & *(-1,0,1) \end{bmatrix} \ ,\qquad \begin{bmatrix} *(-2,-1,0,1,2) & *(-2,-1,0,1,2)\\ 1 & *(-1,0,1) \end{bmatrix} \ . $$ In both cases, the products on the diagonals have absolute values $\le 2$, so their difference is in absolute value at most $4$.

It is now simple to find an answer with determinant $4$, to be convinced that it is possible, e.g. $$ \begin{bmatrix} 1 & -1 & 0\\ 1 & 1 & -1\\ 1 & 1 & 1 \end{bmatrix} \ . $$ The computer check is a one-liner, sage:

sage: max( [matrix(3,3,list(x)).det() for x in cartesian_product([[-1,0,1] for _ in range(9)]) ] )
4