Separating completely independent systems of BooleanCountingFunctions

Question

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.)

Answer 1

First, it is always helpful to provide Mathematica code that can be copied. Please do so in the future.

You can model connecting entries in the same column using a left vector dot product, and connecting entries in the same row using a right vector product. Here is the unaugmented version of your matrix:

m = {
    {0,1,1,1,0,0,0,0,0,0,0,0},
    {0,0,0,1,1,0,0,0,0,0,0,0},
    {1,0,0,0,0,1,0,0,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,1,0,0},
    {1,0,0,0,0,1,0,0,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,1,0,0},
    {0,0,0,0,0,1,1,0,0,0,1,0},
    {0,0,0,0,0,0,0,1,1,1,0,1},
    {0,0,0,0,0,0,0,0,1,1,0,0}
    };
m //TeXForm

$\left( \begin{array}{cccccccccccc} 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \end{array} \right)$

To get all columns that are connected to the first row, use a left dot product with the vector {1, 0, 0, 0, 0, 0, 0, 0, 0}:

v = {1, 0, 0, 0, 0, 0, 0, 0, 0} . m

{0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}

Next, to get all rows that are connected to these columns, use a right dot product with the above vector:

m . v

{3, 1, 0, 0, 0, 0, 0, 0, 0}

Now, we just repeat, although to come to a fixed point it will be necessary to Unitize the vectors after each step. Here is the step function that does a left and right dot product:

step[m_][{r_, c_}] := With[{new = r . m}, Unitize[{m . new, new}]]

Using FixedPoint with the above function yields:

e1 = FixedPoint[step[m], {{1, 0, 0, 0, 0, 0, 0, 0, 0}, 1}]

{{1, 1, 0, 1, 0, 1, 0, 1, 1}, {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1}}

The first list represents the rows that should be extracted, and the second list represents the columns that should be extracted. We can use the following function to convert to row and column indices:

toIndices[bool_] := With[{r = Range @ Length @ bool},
    Pick[r, bool, 1]
]

Then, the first extracted matrix is:

m[[toIndices @ First @ e1, toIndices @ Last @ e1]] //TeXForm

$\left( \begin{array}{cccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{array} \right)$

This agrees the example in the OP. The second matrix can be extracted in the same way:

e2 = FixedPoint[step[m], {{0, 0, 1, 0, 0, 0, 0, 0, 0}, 1}]

{{0, 0, 1, 0, 1, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0}}

and the extracted matrix is:

m[[toIndices @ First @ e2, toIndices @ Last @ e2]] //TeXForm

$\left( \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ \end{array} \right)$