Expansion Minimization

The determinant of a square matrix $A$ is typically defined in terms of cofactor expansion along the first row of $A$.  Then cofactor expansion along other rows or along columns is defined, and shown (or stated) to be equal to the determinant.  Following that, there is usually an example of a matrix that contains at least one zero.  This example is used to illustrate that sometimes, if we choose the appropriate row or column to expand along (namely, one with zeros), we can reduce work needed to compute the determinant using cofactor expansion.

It is certainly easy to tell which row(s) or column(s) to expand along to minimize the number of cofactors it is necessary to compute at each step.  Simply expand along a row or column that has the most zeros.

But what row or column should we expand along to minimize the total number cofactors to compute overall?  Or, to put it in more practical terms, what row or column should we expand along to minimize the
 amount of writing necessary?

Something to consider is that there are two ways to get a zero in the cofactor expansion.  If $B$ is some square submatrix encountered in the cofactor expansion of $A$, then either $b_{ij}=0$ or $\det B_{ij}=0$ ($B_{ij}$ being the $(i,j)-minor of $B$) to make a cofactor.  Since determining whether or not $\det B_{ij}=0$ requires a determinant computation, we would probably want to know the answer to the question to answer the question, which leads to circular reasoning.  So we'll assume that we're basing our expansion minimization strategy purely on which entries of $A$ are 0.

Of course, the answer to the question posed here is mostly useless for practical purposes, since nobody is going to compute the determinant through cofactor expansion for all but the smallest matrices.


But since we frequently present these example and pose these problems to students, with the expectation that they'll know what the best row or column is to expand along, I wonder if there's actually some way to tell what the best path to the determinant is from the matrix itself.

Coefficient Operation

The trace of a matrix satisfies the following equation
$$tr(A+B)=tr(A)+tr(B)$$
The trace is also the coefficient of the second highest power of the characteristic polynomial (up to a factor of $-1$).

The determinant of a matrix satisfies the following equation
$$det(AB)=det(A)det(B)$$
The determinant is also the constant term of the characteristic polynomial (up to a factor of $-1$).

Thus, for both the trace and the determinant functions, there is a binary operation that is defined for both matrices and numbers, and the functions distribute over the corresponding binary operations.  Furthermore, both functions appear in the characteristic polynomial.

If the matrix is 3x3 or larger, then there are many coefficients between that of the determinant and that the second highest power.  We can think of these as generalizations of the trace and determinant.

That is, suppose that $f_k(A)$ is the coefficient of $\lambda^k$ in the characteristic polynomial $p(\lambda)$ of the $n\times n$ matrix $A$.  Then $tr(A)=f_{n-1}(A)$ and $det(A)=f_0(A)$.

That leads to the following question.  For each of the $k$, does there exist a binary operation, say $\circ_k$, that is defined for both square matrices and numbers such that $f_k(A\circ_k B)=f_k(A)\circ_k f_k(B)$ (up to a factor of $-1$)?  Note that we want $A\circ_k B$ to be a matrix and $a\circ_k b$ to be a number.

We can take $\circ_{n-1}$ to be the trace function and $\circ_0$ to be the determinant function, so the answer is yes for $k=n-1$ and $k=0$.

The coefficient of $\lambda^n$ is always $\pm 1$.  Define $\circ$ by $a\circ b=1$ and $A\circ B=I$.  Then $f_n(A\circ B)=f_n(I)=1$ and $f_n(A)\circ f_n(B)=1\circ 1=1$.  Thus,
$$f_n(A\circ B)=f_n(A)\circ f_n(B)$$
So we could take $\circ_n$ to be the binary operation $\circ$ defined here.  So the answer is yes for $k=n$ as well.  Note that $a\circ b$ must be defined to be 1 in order to satisfy the desired property, but $A\circ B$ could be defined to be any matrix, since $f_n$ is always $\pm 1$. 

What can be said about $\circ_k$ for $k\in\{1,\ldots,n-2\}$?

There was some freedom in how we defined $\circ_n$.  It is not unique.  Is this true about the other $\circ_k$, if they even exist?