Filling $4 \times 4$ matrix with Boolean values

Question

In how many ways can we fill a $4 \times 4$ matrix with only $0$'s and $1$'s such that all columns and rows contain an odd number of $1$'s?

I did it in the following way:

I can fill the $3 \times 3$ gray area in $2^9 = 512$ ways and then adjust the entries in the yellow regions such that each row and each column eventually contains an odd number of $1$'s.

Then I observed the following:

Region A and B, the sum of bits in each of the regions must be odd. Therefore both yellow regions must be either odd or even at the same time. So, there is no conflict in the left bottom corner position. Finally, my answer is $512$. Is it correct?

I would like to know other counting technique for this particular problem.

Thanks!

Answer 1

I would solve this question as follows. Since every column must contain an odd number of $1$'s, the number of $1$'s is restricted to $4$, $6$, $8$, $10$ and $12$. We only need to distinguish three cases, since $4$ and $12$ and $6$ and $10$ are each other's inverse. Distinguishing three cases:

1. Four $1$'s. Every column and row contains exactly one $1$, so the number of possible arrangements equals: $$4! = 24$$

2. Six $1$'s. One column contains three $1$'s, the three others contain one $1$. Once the former $1$'s have been placed in the grid, either all three remaining $1$'s are placed in the empty row and columns, or one $1$ is placed in the empty row and columns, and two $1$'s are placed in one of the non-empty rows. The number of possible arrangements thus equals: $${4 \choose 1}{4 \choose 3}\bigg(1+{3 \choose 1}{3 \choose 2}\bigg) = 4 \cdot 4 \cdot (1 + 3 \cdot 3) = 160$$

3. Eight $1$'s. Two columns contain three $1$'s and two columns contain one $1$. The six $1$'s must be distributed over all rows, otherwise it is impossible to have the three rows contain an odd number of $1$'s. Once these $1$'s have been placed in the grid, the remaining two $1$'s must be placed in the rows which contain two $1$'s. As such, the number of possible arrangements equals: $${4 \choose 2}{4 \choose 3}{3 \choose 2}{2 \choose 1} = 6 \cdot 4 \cdot 3 \cdot 2 = 144$$

The total number of arrangements thus equals:

$$24 + 160 + 144 + 160 + 24 = 512$$

Answer 2

We would like to find a matrix $\mathrm X \in \mathbb F_2^{4 \times 4}$ such that $\mathrm X 1_4 = 1_4$ and $1_4^{\top} \mathrm X = 1_4^{\top}$. Vectorizing, we obtain a system of $8$ linear equations in $16$ unknowns

$$\begin{bmatrix} 1_4^\top \otimes \mathrm I_4\\ \mathrm I_4 \otimes 1_4^\top\end{bmatrix} \mbox{vec} (\mathrm X) = \begin{bmatrix} 1_4\\ 1_4\end{bmatrix}$$

Using Gaussian elimination (over $\mathbb F_2$), we eventually obtain the augmented matrix in RREF

$$\left[\begin{array}{cccccccccccccccc|c} \boxed{1} & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0\\ 0 & \boxed{1} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & \boxed{1} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & \boxed{1} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & \boxed{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \boxed{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \boxed{1} & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\end{array}\right]$$

Visual inspection of the augmented matrix in RREF allows us to conclude that the linear system is consistent, that none of the columns corresponding to non-pivot variables are all-zero and that

$$\mbox{rank} \begin{bmatrix} 1_4^\top \otimes \mathrm I_4\\ \mathrm I_4 \otimes 1_4^\top\end{bmatrix} = 7$$

Thus, we have $16 - 7 = 9$ degrees of freedom and $\color{blue}{2^9 = 512}$ solutions.

---

Addendum

Adding the 1st, 2nd, 5th and 6th columns of the augmented matrix in RREF produces the zero vector. Adding the 1st, 3rd, 5th and 7th columns of the augmented matrix in RREF also produces the zero vector. Proceeding in this manner, we can easily find a basis for the $9$-dimensional null space.

Unvectorizing each basis vector, we obtain the $9$ basis matrices

$$\mathrm N_1 := \begin{bmatrix} 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_2 := \begin{bmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_3 := \begin{bmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 1 & 0 & 0\end{bmatrix}$$

$$\mathrm N_4 := \begin{bmatrix} 1 & 0 & 1 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_5 := \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_6 := \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0\end{bmatrix}$$

$$\mathrm N_7 := \begin{bmatrix} 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_8 := \begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\end{bmatrix} \qquad \qquad \mathrm N_9 := \begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1\end{bmatrix}$$

Hence, the set of all $2^9 = 512$ solutions of $\mathrm X 1_4 = 1_4$ and $1_4^{\top} \mathrm X = 1_4^{\top}$ can be generated as follows

$$\left\{ \mathrm X_p + \sum_{k=1}^9 z_k \mathrm N_k \,\, \bigg| \,\, z_k \in \{0,1\} \right\}$$

where $\mathrm X_p$ is a particular solution, e.g.,

$$\mathrm X_p := \begin{bmatrix} 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1\end{bmatrix}$$

Answer 3

I wrote a script in Swift that solves this question and prints the answer, and yes, the answer is $512$.

var matrix: [Bool] = [
    false,false,false,false,
    false,false,false,false,
    false,false,false,false,
    false,false,false,false
]

var shouldContinue: Bool = true
var numberOfValidMatrices: Int = 0

func changeMatrixNumbers() {
    for a in 0 ... 15 {
        if matrix[a] == false {
            matrix[a] = true
            if a > 0 {
                for b in 0 ... a - 1 {
                    matrix[b] = false
                }
            }
            break
        } else if a == 15 {
            shouldContinue = false
        }
    }
}

func isMatrixValid() -> Bool {
    // Rows
    for a in 0 ... 3 {
        var k: Bool = false
        for b in 0 ... 3{
            if matrix[4 * a + b] == true {
                k = k ? false : true
            }
        }
        if !k {
            return false
        }
    }
    // Columns
    for a in 0 ... 3 {
        var k: Bool = false
        for b in 0 ... 3 {
            if matrix[a + 4 * b] == true {
                k = k ? false : true
            }
        }
        if !k {
            return false
        }
    }
    return true
}

while shouldContinue {
    changeMatrixNumbers()
    if isMatrixValid() {
        numberOfValidMatrices += 1
    }
}

print(numberOfValidMatrices)

It can be run here.