# How to multiply a matrix of bits with another?

For example, assume I have two 4x4 matrices of bits:

1 1 1 1       1 1 1 0

0 0 0 0       0 1 1 1

1 0 0 1       1 0 1 1

0 1 1 1       1 0 1 0


I want to apply matrix multiplication for the modified IDEA (International Data Encryption Algorithm). How does one multiply a matrix of bits with another matrix of bits?

Multiplication of bits matrices works just like multiplication of number matrices, except the rule of addition is modified to: $1+1\mapsto 0$.
Let $U$ (resp. $V$) be a square matrix of $n\times n$ elements noted $u_{l,c}$ (resp. $v_{l,c}$) with $1\le l\le n$ and $1\le c\le n$. The product $U\cdot V$ is a square matrix $W$ of $n\times n$ elements noted $w_{l,c}$, with $w_{l,c}=\sum_{j=1}^n u_{l,j}\cdot v_{j,c}$
In the problem at hand, $n=4$. To compute the bit at (say) the third line and first column in the result, we'll use the above formula with $l=3$ and $c=1$, giving $w_{3,1}=\sum_{j=1}^4 u_{3,j}\cdot v_{j,1}$, that is $w_{3,1}=(u_{3,1}\cdot v_{1,1})+(u_{3,2}\cdot v_{2,1})+(u_{3,3}\cdot v_{3,1})+(u_{3,4}\cdot v_{4,1})$. The third line of the left matrix gives $u_{3,1}=1$, $u_{3,2}=0$, $u_{3,3}=0$, $u_{3,4}=1$. The first column of the right matrix gives $v_{1,1}=1$, $v_{2,1}=0$, $v_{3,1}=1$, $v_{4,1}=1$. Thus $w_{3,1}=(1\cdot1)+(0\cdot0)+(0\cdot1)+(1\cdot1)$. That simplifies to $w_{3,1}=1+0+0+1$, then $w_{3,1}=0$.