The end game

The first step of the end game is to run NCProcess2 on the last spreadsheet which was produced in §17.3. The aim of this run of NCProcess2 is to shrink the spreadsheet as aggressively as possible without destroying important information. The spreadsheet produced by NCProcess2 is the same as the last spreadsheet which was produced ⁴in §17.3.

Note that it is necessary that all of the equations in the spreadsheet have solutions, since they are implied by the original equations. The equations involving only knowns play a key role. In particular, they say precisely that, there must exist a projection $P_1$ such that

$$P_1 A P_1=P_1 A P_1 B C P_1=P_1 A-A P_1+B C P_1$$ (4)

are satisfied.

The converse is also true and can be verified with the assistance of the above spreadsheet. To do this, we assume that the matrices $A$, $B$, $C$ and $P_1$ are given and that (17.4) holds, and wish to define $m_1$, $m_2$, $n_1$, $n_2$, $a$, $b$, $c$, $e$, $f$ and $g$ such that each of the equations in the above spreadsheet hold. If we can do this, then each of the equations from the starting polynomial equations $(FAC)$ given in §17.2 will hold and we will have shown that a minimal factorization of the $[A,B,C,1]$ system exists.

(1) Since $P_1^2 = P_1$, it is easy to show that there exists (not necessarily square) matrices $m_1$ and $n_1$ such that $n_1 m_1 = 1$ and $m_1 n_1 = P_1$. These are exactly the equations in the $\{n_1,m_1\}$-Category of the above spreadsheet.

(2) Since $(1-P_1)^2 = 1-P_1$, it is easy to show that there exists (not necessarily square) matrices $m_2$ and $n_2$ such that $n_2 m_2 = 1$ and $m_2 n_2 = 1- P_1$. These are exactly the equations in the $\{n_2,m_2\}$-Category of the above spreadsheet together with the equations in the $\{n_2,m_2,n_1,m_1\}$-Category of the above spreadsheet.

(3) Since we have defined $m_1$, $m_2$, $n_1$ and $n_2$, we can define $a$, $b$, $c$, $e$, $f$ and $g$ by setting $a = n_1 A m_1$, $b = n_1 B$, $c = C m_1$, $e = n_2 A m_2$, $f = n_2 B$ and $g = C m_2$. These are exactly the equations in the singleton category.

Here we have used the fact that we are working with matrices and not elements of an abstract algebra.

With the assignments made above, every equation in the spreadsheet above holds. Thus, by backsolving through the spreadsheet, we have constructed the factors of the original system $[A,B,C,1]$. This proves

Theorem ([BGKvD]) The system $[A,B,C,1]$ can be factored if and only if there exists a projection $P_1$ such that $P_1 A P_1=P_1 A$ and $P_1 B C P_1=P_1 A-A P_1+B C P_1$.

Note that the known equations can be neatly expressed in terms of $P_1$ and $P_2=1-P_1$. Indeed, it is easy to check with a little algebra that these are equivalent to (17.1). It is a question of taste, not algebra, as to which form one chooses.

For a more complicated example of an end game, see §20.4.