# Zhegalkin matrix

The Zhegalkin matrix is an infinite binary matrix.

It is closely related to the infinite integer matrix of Gray code permutation powers () and to the algebraic normal form of Boolean functions.
(Ivan Zhegalkin was the inventor of the ANF. The naming choices made here are new.)

Its colums are the truth tables of all Boolean functions. The column number is the Zhegalkin index of the respective Boolean function.

Its rows are a subset of the Walsh functions, namely the XORs of atoms forming a Sierpiński triangle ().

## Zhegalkin permutations

 ${\displaystyle n}$ ${\displaystyle 2^{n}\times 2^{2^{n}}}$ 0 1 2 3 4 1×2 2×4 4×16 8×256 16×65536

For arity ${\displaystyle n}$ the map from ANFs to truth tables gives a finite Zhegalkin matrix of size ${\displaystyle 2^{n}\times 2^{2^{n}}}$. (It is the top left corner of the infinite matrix.)

It can be interpreted as a permutation of the integers ${\displaystyle 0~...~2^{2^{n}}-1}$, which shall be called Zhegalkin permutation ${\displaystyle \Pi _{n}}$.

It is a self-inverse Walsh permutation of degree 2n. The corresponding element of GL(2n, 2) is the lower Sierpiński triangle.
Π2 is a Walsh permutation of degree 4, and permutes the integers 0 ... 15. The corresponding element of GL(4, 2) is the 4×4 lower Sierpiński triangle.

${\displaystyle \Pi }$ = triangle :     (fixed points in parentheses)

     k   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
n
0       (0) (1)
1       (0)  3  (2)  1
2       (0) 15  10   5  12   3  (6)  9  (8)  7   2  13   4  11 (14)  1


## fixed points

 ${\displaystyle n}$ ${\displaystyle 2^{2^{n-1}}}$ 1 2 3 4 5 2 4 16 256 65536

${\displaystyle \Phi }$ = triangle :

     k  0   1   2   3   4   5   6    7    8    9   10   11   12   13   14   15
n
0       0   1
1       0   2
2       0   6   8  14
3       0  30  40  54  72  86  96  126  128  158  168  182  200  214  224  254

illustrations of rows 3 and 4

The images show how ${\displaystyle \Phi _{n}}$ is derived from ${\displaystyle \Pi _{n-1}}$, the permutation of the same length.
The long matrices have two halves:
In the upper half the bit pattern in column ${\displaystyle k}$ is that of ${\displaystyle \Xi _{n-1,~k}~=~\Pi _{n-1,~k}\oplus k}$.    (Compare triangle Ξ in the next section.)
The bit pattern in the lower half is identical to that of the gray column indices.

${\displaystyle \Phi _{n,~k}~~=~~\Xi _{n-1,~k}+{\bigl (}2^{2^{n-1}}\cdot k{\bigr )}~~=~~{\bigl (}\Pi _{n-1,~k}\oplus k{\bigr )}+{\bigl (}2^{2^{n-1}}\cdot k{\bigr )}}$

The small matrices on the left are divided in the same way:
The upper half is a Sierpiński triangle without the main diagonal, and the lower half is the main diagonal.

Let ${\displaystyle \mathrm {P} (n)=2^{(2^{n}-1)}}$ = (n+1).
Each row contains the unique power of two P(n) in position P(n−1):     ${\displaystyle \Pi _{n,~\mathrm {P} (n-1)}=\mathrm {P} (n)}$

## value XOR place

The triangle of fixed points has a second relationship with the triangle of Zhegalkin permutations.

${\displaystyle \Xi _{n,~k}~~=~~\Pi _{n,~k}\oplus k}$:

     k   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
n
0        0   0
1        0   2   0   2
2        0  14   8   6   8   6   0  14   0  14   8   6   8   6   0  14


For ${\displaystyle n\geq 1}$ the values in row n are repetitions of the fixed points. E.g. row 2 contains the values 0, 6, 8, 14 (each repeated four times).

The set of places ${\displaystyle I_{n,~k}}$ where row n of this triangle has entries ${\displaystyle \Phi _{n,~k}}$ can be calculated by XORing the entry ${\displaystyle \Pi _{n-1,~k}}$ with the entries of ${\displaystyle \Phi _{n}}$.

${\displaystyle I_{n,~k}~~=~~\{i\mid \Pi _{n,~i}\oplus i=\Phi _{n,~k}\}~~=~~\{\Pi _{n-1,~k}\oplus f\mid f\in \Phi _{n}\}}$