Is there some sort of property which helps to get a recursion or pattern in finding determinants for higher order cases?

Solution 1:

Consider this $3 \times 3$ matrix as an example $$ \begin{array}{l} \left( {\begin{array}{*{20}c} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ \end{array}} \right)\left( {\begin{array}{*{20}c} 0 & 0 & 1 \\ {1/2} & {1/2} & 0 \\ 0 & {1/2} & {1/2} \\ \end{array}} \right) \\ {\bf M} = {\bf \Lambda }\,{\bf S} \\ \end{array} $$

The diagonal matrix $\bf \Lambda$ will have entries equal to $1,2$, corresponding to the number of ones in the corresponding row of $\bf M$.

The matrix $\bf S$ is a (right) Stochastic matrix.
As such, all of its eigenvalues have absolute value in $[0,1]$.

Therefore for the general case $n \times n$ , if $0 \le r \le n$ denotes the number of rows with two ones, we can say that $$ - 2^{\,r} \le \left| {\bf M} \right| \le 2^{\,r} $$

And considering the transpose as well we get $$ 0 \le \left| {{\bf MM}^T } \right| = \left| {\bf M} \right|^2 \le 2^{\,r + c} $$ $c$ being the number of columns with two ones.

Concerning a way to compute the determinant, given the matrix $\bf M$ you can always permute the rows so as to bring on top those having only one 1. And after that permute the columns so that the upper part above gets divided into a block $\bf A$ which is necessarily upper triangular and into a null block $\bf 0$.
For instance $$ \left( {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array}} \right) \Rightarrow \left( {\begin{array}{cc|ccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ \end{array}} \right) = \left( {\begin{array}{*{20}c} {\bf A} & 0 \\ {\bf C} & {\bf D} \\ \end{array}} \right) $$

So that the determinant becomes $$ \det \left( {\begin{array}{*{20}c} {\bf A} & 0 \\ {\bf C} & {\bf D} \\ \end{array}} \right) = \det \left( {\bf A} \right)\det \left( {\bf D} \right) = \det \left( {\bf D} \right) $$ If the sign of the determinant is of interest, then the sign of the row/column permutations effected should be taken into account.

Solution 2:

Given a matrix $M$, the determinant:

$$\det(M) = \sum_{\sigma \in S_n} sgn(\sigma) \prod_i M_{i,\sigma(i)}$$

That product term, $\prod\limits_i M_{i,\sigma(i)}$ is essentially the product of the entries of $M$ in positions where the permutation matrix of $\sigma$ has a $1$. For a $\{0,1\}$-matrix, this product is usually $0$, and only $1$ if all of the entries $M_{i,\sigma(i)}$ are $1$s. in other words, if the permutation matrix for $\sigma$ can be gotten by zeroing out entries of $M$.

This process of zeroing out entries of $M$ to produce a permutation matrix feels a bit like a pen-and-paper puzzle. Suppose $$M = \begin{bmatrix}0&0&1&1&0\\0&0&0&1&1\\0&0&1&0&1\\1&1&0&0&0\\0&1&0&0&0\end{bmatrix}.$$ Our goal is to zero out some of the ones to produce a permutation matrix. Starting at the leftmost column, we conclude that $1$ must be part of the solution, so there can be no more $1$s in the fourth row, so we must zero out the $1$ in the fourth row, second column. In the third column, each of those $1$s could be part of a valid solution, but once we guess which of those to zero out, it determines everything else. Hence the only two $\sigma$ for which the product term is nonzero are those whose permutation matrices are:

$$\begin{bmatrix}0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\1&0&0&0&0\\0&1&0&0&0\end{bmatrix}$$ and $$\begin{bmatrix}0&0&0&1&0\\0&0&0&0&1\\0&0&1&0&0\\1&0&0&0&0\\0&1&0&0&0\end{bmatrix}.$$

And I suspect this is a demonstration of all that could happen in the solving process:

• Some $1$s are forced by being the only $1$ in their row/column, and some $1$s are forced as a consequence of that.
• Some $1$s are free to be picked, but once picked form a cascade that "loops around", in the sense that if we hadn't made that first guess, later conclusions in the cascade would force that first guess anyway. Note that the permutation matrices we found both have positive sgn, so the determinant of $M$ is 2.

I produced the 3x3 submatrix in the top right by taking two permutation matrices on three elements with the same sgn that were entirely disjoint and adding them together. You can't do this with 2x2 matrices, but can for larger nxn. If you have several of these appearing, you can get plus or minus powers of 2 for your determinant:

$$\det\begin{bmatrix}0&0&0&1&1&0\\0&0&0&0&1&1\\0&0&0&1&0&1\\1&1&0&0&0&0\\0&1&1&0&0&0\\1&0&1&0&0&0\end{bmatrix} = -4$$

But really, we're only interesting in counting the number of two-choice-cascades with the same sgn (it may be comforting to permute the rows and columns to separate these in a block matrix fashion).

As such, the possible determinants are $0$, and plus or minus powers of 2 from $2^0$ to $2^m$ where $m$ is the number of dimensions divided by 3, rounded down.