I have an augmented matrix as a representation of many instances of BooleanCountingFunction[{k},n][vars]
, and I want to separate it out into many smaller subsystems that don't share any variables (without losing track of what those variables are), as it generally seems significantly faster to use RowReduce
or FindInstance
(the two main procedures I am using) on many smaller sets of equations than one larger set. (Correct me if I am wrong, especially because I suspect that using a SparseArray
for the RowReduce
procedure may be just as fast for combined systems as it would be for separated ones.)
Since the only problem for me is the implementation, here is an example of how I might do things. Suppose this is the starting matrix:
$$\begin{bmatrix}0&1&1&1&0&0&0&0&0&0&0&0&1\\0&0&0&1&1&0&0&0&0&0&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\0&0&0&0&0&1&1&0&0&0&1&0&1\\0&0&0&0&0&0&0&1&1&1&0&1&2\\0&0&0&0&0&0&0&0&1&1&0&0&1\\a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9&a_{10}&a_{11}&a_{12}&\_\end{bmatrix}$$
where the $a_n$ represent location data that I wish to track. (The value in the lower-right corner doesn't matter; for all I care, it doesn't have to even exist.) Start by highlighting any non-zero entry in the first row:
$$\begin{bmatrix}0&1&1&(1)&0&0&0&0&0&0&0&0&1\\0&0&0&1&1&0&0&0&0&0&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\0&0&0&0&0&1&1&0&0&0&1&0&1\\0&0&0&0&0&0&0&1&1&1&0&1&2\\0&0&0&0&0&0&0&0&1&1&0&0&1\\a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9&a_{10}&a_{11}&a_{12}&\_\end{bmatrix}$$
Highlight any other non-zero entries that share the same row or column as the already highlighted entries (except if such an entry is in the last row or column, as this whole process then wouldn't accomplish anything):
$$\begin{bmatrix}0&(1)&(1)&(1)&0&0&0&0&0&0&0&0&(1)\\0&0&0&(1)&1&0&0&0&0&0&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&1&0&0&0&0&1&0&0&1\\0&0&0&0&0&1&1&0&0&0&1&0&1\\0&0&0&0&0&0&0&1&1&1&0&1&2\\0&0&0&0&0&0&0&0&1&1&0&0&1\\a_1&a_2&a_3&(a_4)&a_5&a_6&a_7&a_8&a_9&a_{10}&a_{11}&a_{12}&\_\end{bmatrix}$$
Repeating this until no more new highlights occur should result in this:
$$\begin{bmatrix}0&(1)&(1)&(1)&0&0&0&0&0&0&0&0&(1)\\0&0&0&(1)&(1)&0&0&0&0&0&0&0&(1)\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&(1)&0&0&0&0&(1)&0&0&(1)\\1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&0&(1)&0&0&0&0&(1)&0&0&(1)\\0&0&0&0&0&1&1&0&0&0&1&0&1\\0&0&0&0&0&0&0&(1)&(1)&(1)&0&(1)&(2)\\0&0&0&0&0&0&0&0&(1)&(1)&0&0&(1)\\a_1&(a_2)&(a_3)&(a_4)&(a_5)&a_6&a_7&(a_8)&(a_9)&(a_{10})&a_{11}&(a_{12})&\_\end{bmatrix}$$
Separate out the highlighted entries into their own matrix, taking any zeroes as needed along the way:
$$\begin{bmatrix}1&1&1&0&0&0&0&0&1\\0&0&1&1&0&0&0&0&1\\0&0&0&1&0&0&1&0&1\\0&0&0&1&0&0&1&0&1\\0&0&0&0&1&1&1&1&2\\0&0&0&0&0&1&1&0&1\\a_2&a_3&a_4&a_5&a_8&a_9&a_{10}&a_{12}&\_\end{bmatrix}$$
leaving this matrix behind:
$$\begin{bmatrix}1&1&0&0&1\\1&1&0&0&1\\0&1&1&1&1\\a_1&a_6&a_7&a_{11}&\_\end{bmatrix}$$
Repeating this process confirms that this latter matrix cannot be split apart further.
As for the implementation, I do know that it would likely take the form of a FixedPoint
inside another FixedPoint
, or something similar; the part that I don't have much of a clue about is the highlighting procedure. (Achieving separation from the set of BooleanCountingFunctions
is also permissible.)
(While it is possible to subtract the ninth equation from the eighth to send $a_8$ and $a_{12}$ to a third matrix, that opens up a whole can of worms about intersecting subsets that I don't really want to get into right now.)