View source for Zhegalkin matrix

{{Boolf header}}
{{Zhegalkin stuff}}
The '''Zhegalkin matrix''' is an infinite binary matrix.

It is closely related to the infinite integer matrix of '''[[Gray code permutation powers]]''' ({{oeis|A195467}}) and to the '''[[algebraic normal form]]''' (ANF) of Boolean functions.<br>
<small>({{w|Ivan Zhegalkin}} was the inventor of the ANF. The naming choices made here are new.)</small>

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 {{w|exclusive or|XOR}}<nowiki>s</nowiki> of atoms forming a {{w|Sierpiński triangle}} ({{oeis|A001317}}).

[[File:Zhegalkin 256.svg|thumb|left|1300px|The columns of the 8×256 Zhegalkin matrix are the truth tables of the 256 3-ary Boolean functions.<br><small>The 8×256 matrix above are the colum indices in <nowiki>little-</nowiki>{{w|Endianness|endian}} binary. On the left are the Sierpiński triangle and the row indices.</small>]]
{{clear}}
{{Collapsible START|as rows of a binary Walsh matrix|collapsed}}
This is a 256×256 binary {{w|Walsh matrix}}. Each row is the {{w|Variadic function|variadic}} XOR of the atoms shown in the 256×8 matrix on the left.
[[File:Walsh Zhegalkin 256.svg|1390px]]
{{Collapsible END}}


==Zhegalkin permutation==

{| class="wikitable" style="text-align: center;" style="float: right; text-align: center;"
|+ sizes of finite Zhegalkin matrices
|-
! <math>n</math>
| 0 || 1 || 2 || 3 || 4
|-
! <math>2^n \times 2^{2^n}</math>
| 1×2 || 2×4 || 4×16 || 8×256 || 16×65536
|}

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

It can be interpreted as a permutation of the integers <math>0~...~2^{2^n} - 1</math>,
which shall be called '''Zhegalkin permutation''' <math>\Pi_n</math>.<br>
<small>Keys and values in Π<sub>''n''</sub> shall be called '''[[Zhegalkin twins]]''' &mdash; e.g. 7 and 9 are Zhegalkin twins for arity 2.</small>

It is a self-inverse [[Walsh permutation]] of degree 2<sup>''n''</sup>. The corresponding element of {{w|general linear group|GL}}(2<sup>''n''</sup>, 2) is the {{w|triangular matrix|lower}} Sierpiński triangle.<br>
<small>
Π<sub>2</sub> 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.
</small>

{{Zhegalkin matrix/Triangle Pi}}

In a finite Zhegalkin matrix, the columns with even/odd weight are in the left/right half. &nbsp;
<small>(A truth table has a Zhegalkin twin with odd weight, iff its last digit is true.)</small><br>
<small>Boolean functions whose Zhegalkin index has even/odd weight shall be called {{w|evil number|evil}}/{{w|odious number|odious}}, which shall be called its '''''depravity'''''</small>.

{{Zhegalkin matrix/triangle Pi compressed}}

===fixed points===

{| class="wikitable" style="text-align: center;" style="float: right; text-align: center;"
|+ number of fixed points
|-
! <math>n</math>
| 1 || 2 || 3 || 4 || 5
|-
! <math>2^{2^{n-1}}</math>
| 2 || 4 || 16|| 256 || 65536
|}

The fixed points of Zhegalkin permutations correspond to [[noble Boolean functions]].

{{Zhegalkin matrix/Triangle Phi}}

{{Collapsible START|illustration of fixed points <math>\Phi_3</math> in permutation <math>\Pi_3</math>|collapsed gap-below}}
[[File:Zhegalkin 256; fixed.svg|1320px]]
{{Collapsible END}}

==Python code==


{{Collapsible START|Python functions|collapsed gap-below}}
<source lang="python">
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
</source>
{{Collapsible END}}

{{Algebraic normal form/python}}


[[Category:Boolean functions; Zhegalkin stuff]]