Let $P$ be a $3\times 3$ matrix such that all the entries are from $\{–1, 0, 1\}$. What is the maximum possible value of the determinant of $P$?

Question

Let $P$ be a matrix of order $ 3 \times 3$ such that all the entries in $P$ are from the set $\{–1, 0, 1\}$. What is the maximum possible value of the determinant of $P$?

The original question

This question is from JEE ADVANCED 2018, paper 2

My Attempt: $det(P)$=$$ \begin{vmatrix} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \\ \end{vmatrix}$$ $$a_1(b_2c_3 – b_3c_2)– a_2(b_1c_3 – b_3c_1) + a_3(b_1c_2 – b_2c_1)\le6$$

value can be 6 only if $a_1 = 1, a_2 = \ –1, a_3 = 1 , b_2c_3 = b_1c_3 = b_1c_2 = 1 , b_3c_2 = b_3c_1 = b_2c_1 = \ – 1$ and $(b_2c_3) (b_3c_1) (b_1c_2) = \ – 1$ and $ (b_1c_3)(b_3c_2) (b_2c_1) = 1$

i.e $b_1b_2b_3c_1c_2c_3 = 1$ and $– 1$ hence not possible Similar contradiction occurs when$ a_1 = 1, a_2 = \ –1, a_3 = 1, b_2c_2 = b_3c_1 = b_1c_2 = 1, b_3c_2 = b_3c_1 = b_2c_1 =\ – 1$

Now for value to be $5$ one the terms must be zero but that will make $2$ terms zero which means answer cannot be $5$ Now,$$ \begin{vmatrix} 1 & 0 & 1 \\ -1 & 1 & 1 \\ -1 & -1 & -1 \\ \end{vmatrix} =4$$ Hence max value = $4$

I need the best way to solve this question(the process through which this question could be done in the least time possible and it should not be similar to my approach (i.e any approach other than substitution and checking)

Answer 1

This really isn't the quickest way to solve the problem if you need to write it down, but it's rather efficient if you do it mentally.

Let us relax the domain of the entries of $P$ to the interval $\mathcal I=[-1,1]$ first. If we keep the two last two columns of $P$ fixed, $\det(P)$ is a linear function of the first column. Therefore, when the first column of $P$ ranges over $\mathcal I^3$, the maximum of $\det(P)$ is attainable at a vertex of the cube $\mathcal I^3$. It follows that if $P_0$ is a global maximiser of $\det(P)$ over $\{P:p_{ij}\in\mathcal I\}$, we can always modify its entries on first column to $\pm1$ to obtain a new global maximiser. By doing the similar to the second and the third columns, we obtain a global maximiser whose elements are all equal to $\pm1$. It follows that \begin{aligned} &\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\{-1,0,1\}\}\\ \le&\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\mathcal I\}\\ =&\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\{-1,1\}\}\\ \le&\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\{-1,0,1\}\}. \end{aligned} Hence all maxima in the above are equal and we may consider only those matrices $P$ whose entries are equal to $\pm1$. By Laplace expansion along the first row, the determinant of such a $P$ must be even. Also, by Hadamard's determinant inequality, $\det(P)\le\|p_{\ast1}\|\|p_{\ast2}\|\|p_{\ast3}\|=3\sqrt{3}<6$. Hence $\det(P)$ is at most $4$. Since $$ \det\pmatrix{-1&1&1\\ 1&-1&1\\ 1&1&-1}=4, $$ we conclude that $\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\{-1,0,1\}\}=4$.

Remark. If you are familiar with the Hadamard maximum determinant problem, there is also a standard trick to prove that the determinant of an $n\times n$ $\{-1,1\}$-matrix is $\frac{1}{2^{n-1}}$ times the determinant of an $(n-1)\times(n-1)$ $\{0,1\}$-matrix. Since the maximum determinant of a $2\times2$ $\{0,1\}$-matrix is obviously $1$, we have $\max\{\det(P):P\in M_3(\mathbb R):p_{ij}\in\{-1,1\}\}=4$. But we shall not use this trick here because it will make the answer even longer.

Answer 2

For the determinant to be nonzero, each row and column must have at least one nonzero element. WLOG, we can consider the main diagonal elements to be nonzero (otherwise, swapping can be made).

WLOG, we can consider the main diagonal elements to be $1$ (otherwise, take $-1$ out of determinant).

Do row operations: $$\begin{vmatrix} 1 & a_2 & a_3 \\ b_1 & 1 & b_3 \\ c_1 & c_2 & 1 \\ \end{vmatrix}\stackrel{-b_1R_1+R_2\to R_2\\ -c_1R_1+R_3\to R_3}{=} \begin{vmatrix} 1 & a_2 & a_3 \\ 0 & 1-a_2b_1 & b_3-a_3b_1 \\ 0 & c_2-a_2 c_1 & 1-a_3c_1 \\ \end{vmatrix}$$

Hence, it reduces to: $$\begin{vmatrix} 1-a_2b_1 & b_3-a_3b_1 \\ c_2-a_2 c_1 & 1-a_3c_1 \\ \end{vmatrix}=\begin{vmatrix} k_1 & k_2 \\ k_3 & k_4 \\ \end{vmatrix}$$ For the determinant to exceed $4$, there must be $k_1=k_4=2$ and $(k_2,k_3)=(2,-2), (2,-1) \text{ or } (1,-1)$.

Case $\begin{vmatrix} 2 & 2 \\ -2 & 2 \\ \end{vmatrix} \text{ or } \begin{vmatrix} 2 & 2 \\ -1 & 2 \\ \end{vmatrix}$: $$a_2b_1=a_3c_1=a_3b_1=-1 \Rightarrow a_2c_1=-1 \Rightarrow \\ c_2-a_2c_1\ne -2 \text{ or } -1$$ Case $\begin{vmatrix} 2 & 1 \\ -1 & 2 \\ \end{vmatrix}$: $$a_2b_1=a_3c_1=-1 \Rightarrow a_2b_1a_3c_1=1 \Rightarrow \\ (b_3-a_3b_1)(c_2-a_2c_1)=(0-a_3b_1)(0-a_2c_1)\ne -1$$ Hence, the maximum is $4$. Can you find it and finish?