# Zhegalkin matrix

Ж :
* ANF   matrix   twins
* noble   gentle
* smallest Zhegalkin index
The Zhegalkin matrix is an infinite binary matrix.
It is closely related to the infinite integer matrix of Gray code permutation powers ( A195467) and to the algebraic normal form (ANF) 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 index 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 ( A001317).

## Zhegalkin permutation

sizes of finite Zhegalkin matrices :
| $n$ | 0 | 1 | 2 | 3 | 4 |
| $2^{n}\times 2^{2^{n}}$ | 1×2 | 2×4 | 4×16 | 8×256 | 16×65536 |
For arity $n$ the map from ANFs to truth tables gives a finite Zhegalkin matrix of size $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 $0~...~2^{2^{n}}-1$, which shall be called Zhegalkin permutation $\Pi _{n}$. Keys and values in Π$_n$ shall be called Zhegalkin twins — e.g. 7 and 9 are Zhegalkin twins for arity 2.
It is a self-inverse Walsh permutation of degree 2$^n$. The corresponding element of GL(2$^n$, 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.
$\Pi$           A197819 :
* row 3 of length 256:     0, 255, 170, 85 ... 84, 171, 254, 1
* [0, 255, 170, 85, 204, 51, 102, 153, 136, 119, 34, 221, 68, 187, 238, 17, 240, 15, 90, 165, 60, 195, 150, 105, 120, 135, 210, 45, 180, 75, 30, 225, 160, 95, 10, 245, 108, 147, 198, 57, 40, 215, 130, 125, 228, 27, 78, 177, 80, 175, 250, 5, 156, 99, 54, 201, 216, 39, 114, 141, 20, 235, 190, 65, 192, 63, 106, 149, 12, 243, 166, 89, 72, 183, 226, 29, 132, 123, 46, 209, 48, 207, 154, 101, 252, 3, 86, 169, 184, 71, 18, 237, 116, 139, 222, 33, 96, 159, 202, 53, 172, 83, 6, 249, 232, 23, 66, 189, 36, 219, 142, 113, 144, 111, 58, 197, 92, 163, 246, 9, 24, 231, 178, 77, 212, 43, 126, 129, 128, 127, 42, 213, 76, 179, 230, 25, 8, 247, 162, 93, 196, 59, 110, 145, 112, 143, 218, 37, 188, 67, 22, 233, 248, 7, 82, 173, 52, 203, 158, 97, 32, 223, 138, 117, 236, 19, 70, 185, 168, 87, 2, 253, 100, 155, 206, 49, 208, 47, 122, 133, 28, 227, 182, 73, 88, 167, 242, 13, 148, 107, 62, 193, 64, 191, 234, 21, 140, 115, 38, 217, 200, 55, 98, 157, 4, 251, 174, 81, 176, 79, 26, 229, 124, 131, 214, 41, 56, 199, 146, 109, 244, 11, 94, 161, 224, 31, 74, 181, 44, 211, 134, 121, 104, 151, 194, 61, 164, 91, 14, 241, 16, 239, 186, 69, 220, 35, 118, 137, 152, 103, 50, 205, 84, 171, 254, 1]
In a finite Zhegalkin matrix, the columns with even/odd weight are in the left/right half.  (A truth table has a Zhegalkin twin with odd weight, iff its last digit is true.) Boolean functions whose Zhegalkin index has even/odd weight shall be called evil/odious, which shall be called its depravity.

### fixed points

number of fixed points :
| $n$ | 1 | 2 | 3 | 4 | 5 |
| $2^{2^{n-1}}$ | 2 | 4 | 16 | 256 | 65536 |
The fixed points of Zhegalkin permutations correspond to noble Boolean functions.
$\Phi _{n}~~=~~\{i\mid \Pi _{n,~i}=i\}$           A358167 :
* row 4 of length 256:     0, 510, 680, 854 ... 64680, 64854, 65024, 65534
* [0, 510, 680, 854, 1224, 1334, 1632, 1950, 2176, 2430, 2600, 3030, 3144, 3510, 3808, 3870, 4320, 4382, 4680, 5046, 5160, 5590, 5760, 6014, 6240, 6558, 6856, 6966, 7336, 7510, 7680, 8190, 8320, 8574, 8744, 9174, 9288, 9654, 9952, 10014, 10240, 10750, 10920, 11094, 11464, 11574, 11872, 12190, 12384, 12702, 13000, 13110, 13480, 13654, 13824, 14334, 14560, 14622, 14920, 15286, 15400, 15830, 16000, 16254, 16512, 16766, 16936, 17366, 17480, 17846, 18144, 18206, 18432, 18942, 19112, 19286, 19656, 19766, 20064, 20382, 20576, 20894, 21192, 21302, 21672, 21846, 22016, 22526, 22752, 22814, 23112, 23478, 23592, 24022, 24192, 24446, 24576, 25086, 25256, 25430, 25800, 25910, 26208, 26526, 26752, 27006, 27176, 27606, 27720, 28086, 28384, 28446, 28896, 28958, 29256, 29622, 29736, 30166, 30336, 30590, 30816, 31134, 31432, 31542, 31912, 32086, 32256, 32766, 32768, 33278, 33448, 33622, 33992, 34102, 34400, 34718, 34944, 35198, 35368, 35798, 35912, 36278, 36576, 36638, 37088, 37150, 37448, 37814, 37928, 38358, 38528, 38782, 39008, 39326, 39624, 39734, 40104, 40278, 40448, 40958, 41088, 41342, 41512, 41942, 42056, 42422, 42720, 42782, 43008, 43518, 43688, 43862, 44232, 44342, 44640, 44958, 45152, 45470, 45768, 45878, 46248, 46422, 46592, 47102, 47328, 47390, 47688, 48054, 48168, 48598, 48768, 49022, 49280, 49534, 49704, 50134, 50248, 50614, 50912, 50974, 51200, 51710, 51880, 52054, 52424, 52534, 52832, 53150, 53344, 53662, 53960, 54070, 54440, 54614, 54784, 55294, 55520, 55582, 55880, 56246, 56360, 56790, 56960, 57214, 57344, 57854, 58024, 58198, 58568, 58678, 58976, 59294, 59520, 59774, 59944, 60374, 60488, 60854, 61152, 61214, 61664, 61726, 62024, 62390, 62504, 62934, 63104, 63358, 63584, 63902, 64200, 64310, 64680, 64854, 65024, 65534]