Zhegalkin matrix
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 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 ( A001317).

The 8×256 matrix above are the colum indices in little-endian binary. On the left are the Sierpiński triangle and the row indices.
as rows of a binary Walsh matrix |
---|
This is a 256×256 binary Walsh matrix. Each row is the variadic XOR of the atoms shown in the 256×8 matrix on the left.
|
Zhegalkin permutations[edit | edit source]
0 | 1 | 2 | 3 | 4 | |
1×2 | 2×4 | 4×16 | 8×256 | 16×65536 |
For arity the map from ANFs to truth tables gives a finite Zhegalkin matrix of size . (It is the top left corner of the infinite matrix.)
It can be interpreted as a permutation of the integers , which shall be called Zhegalkin permutation .
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.
= triangle A197819: (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
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] |
fixed points[edit | edit source]
1 | 2 | 3 | 4 | 5 | |
2 | 4 | 16 | 256 | 65536 |
= triangle A358167:
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
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] |
illustration of fixed points in permutation |
---|
row sums: 1, 2, 28, 2032, 8388352... | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
For this is =
|
Let = A058891(n+1).
Each row contains the unique power of two P(n) in position P(n−1):
value XOR place[edit | edit source]
The triangle of fixed points has a second relationship with the triangle of Zhegalkin permutations.
:
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
row 3 of length 256: 0, 254, 168, 86 ... 168, 86, 0, 254 |
---|
[0, 254, 168, 86, 200, 54, 96, 158, 128, 126, 40, 214, 72, 182, 224, 30, 224, 30, 72, 182, 40, 214, 128, 126, 96, 158, 200, 54, 168, 86, 0, 254, 128, 126, 40, 214, 72, 182, 224, 30, 0, 254, 168, 86, 200, 54, 96, 158, 96, 158, 200, 54, 168, 86, 0, 254, 224, 30, 72, 182, 40, 214, 128, 126, 128, 126, 40, 214, 72, 182, 224, 30, 0, 254, 168, 86, 200, 54, 96, 158, 96, 158, 200, 54, 168, 86, 0, 254, 224, 30, 72, 182, 40, 214, 128, 126, 0, 254, 168, 86, 200, 54, 96, 158, 128, 126, 40, 214, 72, 182, 224, 30, 224, 30, 72, 182, 40, 214, 128, 126, 96, 158, 200, 54, 168, 86, 0, 254, 0, 254, 168, 86, 200, 54, 96, 158, 128, 126, 40, 214, 72, 182, 224, 30, 224, 30, 72, 182, 40, 214, 128, 126, 96, 158, 200, 54, 168, 86, 0, 254, 128, 126, 40, 214, 72, 182, 224, 30, 0, 254, 168, 86, 200, 54, 96, 158, 96, 158, 200, 54, 168, 86, 0, 254, 224, 30, 72, 182, 40, 214, 128, 126, 128, 126, 40, 214, 72, 182, 224, 30, 0, 254, 168, 86, 200, 54, 96, 158, 96, 158, 200, 54, 168, 86, 0, 254, 224, 30, 72, 182, 40, 214, 128, 126, 0, 254, 168, 86, 200, 54, 96, 158, 128, 126, 40, 214, 72, 182, 224, 30, 224, 30, 72, 182, 40, 214, 128, 126, 96, 158, 200, 54, 168, 86, 0, 254] |
For 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 where row n of this triangle has entries can be calculated by XORing the entry with the entries of .
example for n = 3 |
---|
The left column is , and the top row is . The entries are their bitwise XORs. [[ 0, 30, 40, 54, 72, 86, 96, 126, 128, 158, 168, 182, 200, 214, 224, 254], [ 15, 17, 39, 57, 71, 89, 111, 113, 143, 145, 167, 185, 199, 217, 239, 241], [ 10, 20, 34, 60, 66, 92, 106, 116, 138, 148, 162, 188, 194, 220, 234, 244], [ 5, 27, 45, 51, 77, 83, 101, 123, 133, 155, 173, 179, 205, 211, 229, 251], [ 12, 18, 36, 58, 68, 90, 108, 114, 140, 146, 164, 186, 196, 218, 236, 242], [ 3, 29, 43, 53, 75, 85, 99, 125, 131, 157, 171, 181, 203, 213, 227, 253], [ 6, 24, 46, 48, 78, 80, 102, 120, 134, 152, 174, 176, 206, 208, 230, 248], [ 9, 23, 33, 63, 65, 95, 105, 119, 137, 151, 161, 191, 193, 223, 233, 247], [ 8, 22, 32, 62, 64, 94, 104, 118, 136, 150, 160, 190, 192, 222, 232, 246], [ 7, 25, 47, 49, 79, 81, 103, 121, 135, 153, 175, 177, 207, 209, 231, 249], [ 2, 28, 42, 52, 74, 84, 98, 124, 130, 156, 170, 180, 202, 212, 226, 252], [ 13, 19, 37, 59, 69, 91, 109, 115, 141, 147, 165, 187, 197, 219, 237, 243], [ 4, 26, 44, 50, 76, 82, 100, 122, 132, 154, 172, 178, 204, 210, 228, 250], [ 11, 21, 35, 61, 67, 93, 107, 117, 139, 149, 163, 189, 195, 221, 235, 245], [ 14, 16, 38, 56, 70, 88, 110, 112, 142, 144, 166, 184, 198, 216, 238, 240], [ 1, 31, 41, 55, 73, 87, 97, 127, 129, 159, 169, 183, 201, 215, 225, 255]] Which places in row 3 of the XOR triangle have the entry ?
|
Python code[edit | edit source]
functions |
---|
from sympy import binomial
def sierpinski(n):
return int(sum([(binomial(n, i) % 2) * 2 ** i for i in range(n + 1)]))
def zhegalkin_perm(n, k):
row_length = 1 << (1 << n) # 2 ** 2 ** n
assert k < row_length
string_length = 1 << n # 2 ** n
k_binary = "{0:b}".format(k).zfill(string_length)
reflected_result = 0
for i, binary_digit in enumerate(k_binary):
if binary_digit == '1':
s = sierpinski(i)
reflected_result ^= s
reflected_result_binary = "{0:b}".format(reflected_result).zfill(string_length)
result_binary = reflected_result_binary[::-1]
return int(result_binary, 2)
def zhegalkin_fixed(n, k):
if n == 0:
assert k < 2
return k
else:
row_length = 1 << (1 << (n-1)) # 2 ** 2 ** (n-1)
assert k < row_length
p = zhegalkin_perm(n-1, k)
p_xor_k = p ^ k
shifted_k = row_length * k
return p_xor_k + shifted_k
|
Walsh permutations and Sierpiński triangles |
---|
The classes used here are part of a project not yet published. A link will be added later. from discretehelpers.walsh_perm import WalshPerm
from discretehelpers.binv import Binv
def anf_int_to_boolf(input_integer):
from discretehelpers.boolf import Boolf
input_indices = Binv(intval=input_integer).indices
if input_indices == set():
return Boolf(False)
result_boolf = Boolf(False)
for i in input_indices:
loop_indices = Binv(intval=i).indices
loop_boolf = Boolf(multi_and=loop_indices)
result_boolf = result_boolf ^ loop_boolf
return result_boolf
def create_sequence(arity):
sequence = []
for i in range(2 ** 2 ** arity):
boolf = anf_int_to_boolf(i)
binv = Binv(boolf.truth_table(arity))
sequence.append(binv.intval)
return sequence
sequence_0 = create_sequence(0)
# [0, 1]
sequence_1 = create_sequence(1)
# [0, 3, 2, 1]
sequence_2 = create_sequence(2)
# [0, 15, 10, 5, 12, 3, 6, 9, 8, 7, 2, 13, 4, 11, 14, 1]
sequence_3 = create_sequence(3)
# [0, 255, 170, 85 ... 84, 171, 254, 1]
sequence_4 = create_sequence(4)
# [0, 65535, 43690, 21845 ... 21844, 43691, 65534, 1]
wp_0 = WalshPerm(perm=sequence_0)
wp_1 = WalshPerm(perm=sequence_1)
wp_2 = WalshPerm(perm=sequence_2)
wp_3 = WalshPerm(perm=sequence_3)
wp_4 = WalshPerm(perm=sequence_4)
wp_0.matrix()
# array([[1]])
wp_1.matrix()
# array([[1, 0],
# [1, 1]])
wp_2.matrix()
# array([[1, 0, 0, 0],
# [1, 1, 0, 0],
# [1, 0, 1, 0],
# [1, 1, 1, 1]])
wp_3.matrix()
# array([[1, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 0, 0, 0],
# [1, 1, 1, 1, 0, 0, 0, 0],
# [1, 0, 0, 0, 1, 0, 0, 0],
# [1, 1, 0, 0, 1, 1, 0, 0],
# [1, 0, 1, 0, 1, 0, 1, 0],
# [1, 1, 1, 1, 1, 1, 1, 1]])
wp_4.matrix()
# array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
# [1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0],
# [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
# [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
# [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],
# [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]])
|