Chapter 15

Binary Matrices

[12/67%]

Show

LaTeX

Show LaTeX

Problem 15.1.1

Consider the four $2 \times 2$ binary matrices

A = \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}, \quad C = \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \quad D = \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}

with the underlying field $\mathbb {F}$ , $\operatorname {char}(\mathbb {F}) = 2$ . Find $A+B+C+D$ and $ABCD$ .

Problem 15.1.2

(i)(ii)

For a $2 \times 2$ binary matrix

A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}, \quad a_{jk} \in \left\{ 0,1\right\}

we define the determinant as

\operatorname {det}\left(A\right) = (a_{11} \cdot a_{22}) \oplus (a_{12} \cdot a_{21})

where $\cdot$ is the AND-operation and $\oplus$ is the XOR-operation.

(i)

Find the determinant for the following $2 \times 2$ matrices

\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}.

(ii)

Find the determinant for the following $2 \times 2$ matrices

\begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}

\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 \\ 1 & 1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}.

Problem 15.1.3

(i)(ii)

The determinant of a $3 \times 3$ matrix $A = (a_{jk})$ is given by

a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{13}a_{22}a_{31} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33}.

For a binary matrix $B$ we replace this expression by

\begin{split} \operatorname {det}\left(B\right) = {} & (b_{11} \cdot b_{22} \cdot b_{33}) \oplus (b_{12} \cdot b_{23} \cdot b_{31}) \oplus (b_{13} \cdot b_{21} \cdot b_{32}) \\ & \oplus (b_{13} \cdot b_{22} \cdot b_{31}) \oplus (b_{11} \cdot b_{23} \cdot b_{32}) \oplus (b_{12} \cdot b_{21} \cdot b_{33}). \end{split}

(i)

Calculate the determinant for the binary matrices

\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.

(ii)

Calculate the determinant for the binary matrices

\begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}.

Problem 15.1.4

The finite field $GF(2)$ consists of the elements $0$ and $1$ (bits) which satisfies the following addition (XOR) and multiplication (AND) tables

\begin{array}{c|cc} \oplus & 0 & 1 \\ \hline 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \qquad \begin{array}{c|cc} \cdot & 0 & 1 \\ \hline 0 & 0 & 0 \\ 1 & 0 & 1 \end{array}

Find the determinant of the binary matrices

A = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.

Problem 15.1.5

A boolean function $f : \left\{ 0,1\right\}^{n} \rightarrow \left\{ 0,1\right\}$ can be transformed from the domain $\left\{ 0,1\right\}$ into the spectral domain by a linear transformation

Ty = s

where $T$ is a $2^{n} \times 2^{n}$ orthogonal matrix, $y = (y_{0}, y_{1}, \ldots , y_{2^{n}-1})^{T}$ , is the two valued ( $\left\{ +1,-1\right\}$ with $0 \leftrightarrow 1$ , $1 \leftrightarrow -1$ ) truth table vector of the boolean function and $s_{j}$ ( $j = 0, 1, \ldots , 7$ ) are the spectral coefficients ( $s = (s_{0}, s_{1}, \ldots , s_{2^{n}-1})^{T}$ ). Since $T$ is invertible we have

T^{-1}s = y.

For $T$ we select the Hadamard matrix. The $2^{n} \times 2^{n}$ Hadamard matrix $H(n)$ is recursively defined as

H(n) = \begin{pmatrix} H(n-1) & H(n-1) \\ H(n-1) & -H(n-1) \end{pmatrix}, \qquad n = 1, 2, \ldots

with $H(0) = (1)$ ( $1 \times 1$ matrix). The inverse of $H(n)$ is given by

H^{-1}(n) = \frac{1}{2^{n}} H(n).

Now any boolean function $f(x_{1}, \ldots , x_{n})$ can be expanded as the arithmetical polynomial

\frac{1}{2^{n+1}} \left(2^{n} - s_{0} - s_{1}(-1)^{x_{n}} - s_{2}(-1)^{x_{n-1}} - \cdots - s_{2^{n}-1}(-1)^{x_{1} \oplus x_{2} \oplus \cdots \oplus x_{n}}\right)

where $\oplus$ denotes the modulo-2 addition.

Consider the boolean function $f : \left\{ 0,1\right\}^{3} \rightarrow \left\{ 0,1\right\}$ given by

f(x_{1}, x_{2}, x_{3}) = \bar{x}_{1} \cdot \bar{x}_{2} \cdot \bar{x}_{3} + \bar{x}_{1} \cdot x_{2} \cdot \bar{x}_{3} + x_{1} \cdot x_{2} \cdot \bar{x}_{3}.

Find the truth table, the vector $y$ and then calculate, using $H(3)$ , the spectral coefficients $s_{j}$ , ( $j = 0, 1, \ldots , 7$ ).

Problem 15.1.6

Consider the binary matrices

A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}.

Calculate the Hadamard product $A \bullet B$ and the star product $A \star B$ .

Problem 15.1.7

A binary Hadamard matrix is an $n \times n$ matrix $M$ (where $n$ is even) with entries in $\left\{ 0,1\right\}$ such that any two distinct rows or columns of $M$ have Hamming distance $n/2$ . The Hamming distance between two vectors is the number of entries at which they differ. Find a $4 \times 4$ binary Hadamard matrix.

Problem 15.1.8

How many $2 \times 2$ binary matrices can one form which contain two $1$ 's? Find the commutator between these matrices.

Section 15.2Supplementary Problems[4/0%]

Problem 15.2.1

How many $3 \times 3$ binary matrices can one form which contain three $1$ 's? Write down these matrices. Which of them are invertible?

Problem 15.2.2

Consider the four $8 \times 8$ binary matrices

S_{0} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \qquad S_{1} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix},

S_{2} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \qquad S_{3} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.

Find the $8 \times 8$ matrices $Q_{0}, Q_{1}, Q_{2}, Q_{3}$ such that

Q_{0} S_{0} Q_{0}^{T} = S_{1}, \quad Q_{1} S_{1} Q_{1}^{T} = S_{2}, \quad Q_{2} S_{2} Q_{2}^{T} = S_{3}, \quad Q_{3} S_{3} Q_{3}^{T} = S_{0}.

Problem 15.2.3

Consider the four $2 \times 2$ binary matrices $A$ and $B$ with the underlying field $\mathbb {F}$ , $\operatorname {char}(\mathbb {F}) = 2$ . Find the condition on $A$ and $B$ such that $A+B = AB$ .

Problem 15.2.4

Consider the two permutation matrices (NOT-gate and XOR-gate)

N = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}, \qquad X = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.

Can we generate all other permutation matrices from these two permutation matrices? Note that $N^{2} = I_{4}$ , $X^{2} = I_{4}$ and

NX = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}, \qquad XN = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}.