CoCalc -- hadamard

GitHub Repository: sagemath/sagelib
Path: blob/master/sage/combinat/matrices/hadamard_matrix.py
⁴⁰⁷² views
1
r"""
2
Hadamard matrices
3

4
A Hadamard matrix is an nxn matrix H whose entries are either +1 or -1 and whose
5
rows are mutually orthogonal. For example, the matrix `H_2` defined by::
6

7
        [ 1  1 ]
8
        [ 1 -1 ]
9

10
is a Hadamard matrix. An  nxn matrix H whose entries are either +1 or -1
11
is a Hadamard matrix if and only if
12
 (a) `|det(H)|=n^(n/2),` or
13
 (b)  `H*H^t = n\cdot I_n`, where `I_n` is the identity matrix.
14
In general, the tensor product of an mxm Hadamard matrix and an `n\times n` Hadamard
15
matrix is an `(mn)\times (mn)` matrix. In particular, if there is an nxn Hadamard
16
matrix then there is a `(2n)\times (2n)` Hadamard matrix (since one may tensor with `H_2`).
17
This particular case is sometimes called the Sylvester construction.
18
The Hadamard conjecture (possibly due to Paley) states that a Hadamard matrix of 
19
order `n` exists if and only if `n=2` or `n` is a multiple of `4`.
20

21
The module below implements the Paley constructions (see for example [3]_) and 
22
the Sylvester construction. It also allows you to pull a Hadamard matrix
23
from the database at [1]_.
24

25
AUTHOR::
26
    -- David Joyner (2009-05-17): initial version
27

28
REFERENCES::
29
  .. [1] N.J.A. Sloane's Library of Hadamard Matrices, at
30
        http://www.research.att.com/~njas/hadamard
31
  .. [2] Hadamard matrices on Wikipedia, at http://en.wikipedia.org/wiki/Hadamard_matrix
32
  .. [3] K. J. Horadam, Hadamard Matrices and Their Applications, Princeton University 
33
        Press, 2006.
34

35
"""
36
from sage.rings.arith import kronecker_symbol
37
from sage.rings.integer_ring import IntegerRing
38
ZZ = IntegerRing()
39
from sage.matrix.constructor import matrix, block_matrix
40
import urllib
41
from sage.misc.functional import is_even
42
from sage.rings.arith import is_prime
43

44
def H1(i,j,p):
45
    """
46
    Returns the i,j-th entry of the Paley matrix, type I case.
47

48
    EXAMPLES::
49
        sage: sage.combinat.matrices.hadamard_matrix.H1(1,2,3)
50
        -1
51
    """
52
    if i==0:
53
        return 1
54
    if j==0:
55
        return -1
56
    if i==j:
57
        return 1
58
    return kronecker_symbol(i-j,p)
59

60

61
def H2(i,j,p):
62
    """
63
    Returns the i,j-th entry of the Paley matrix, type II case.
64

65
    EXAMPLES::
66
        sage: sage.combinat.matrices.hadamard_matrix.H1(1,2,5)
67
        1
68

69
    """
70
    if i==0 and j==0:
71
        return 0
72
    if i==0 or j==0:
73
        return 1
74
    if j==0:
75
        return -1
76
    if i==j:
77
        return 0
78
    return kronecker_symbol(i-j,p)
79

80
def hadamard_matrix_paleyI(n):
81
    """
82
    Implements the Paley type I construction.
83

84

85
    EXAMPLES::
86
        sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyI(4)
87
        [ 1 -1 -1 -1]
88
        [ 1  1  1 -1]
89
        [ 1 -1  1  1]
90
        [ 1  1 -1  1]
91
    """
92
    if is_prime(n-1) and (n-1)%4==3:
93
        p = n-1
94
    else:
95
        raise ValueError, "The order %s is not covered by the Paley type I construction."%n
96
    return matrix(ZZ,[[H1(i,j,p) for i in range(n)] for j in range(n)])
97

98

99
def hadamard_matrix_paleyII(n):
100
    """
101
    Implements the Paley type II construction.
102

103

104
    EXAMPLES::
105
        sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyI(12).det()
106
        2985984
107
        sage: 12^6
108
        2985984
109

110
    """
111
    N = ZZ(n/2)
112
    if is_prime(N-1) and (N-1)%4==1:
113
        p = N-1
114
    else:
115
        raise ValueError, "The order %s is not covered by the Paley type II construction."%n
116
    S = matrix(ZZ,[[H2(i,j,p) for i in range(N)] for j in range(N)])
117
    return block_matrix([[S+1,S-1],[S-1,-S-1]])
118

119
def hadamard_matrix(n):
120
    """
121
    Tries to construct a Hadamard matrix using a combination of Paley and Sylvester 
122
    constructions.
123

124
    EXAMPLES::
125
        sage: hadamard_matrix(12).det()
126
        2985984
127
        sage: 12^6
128
        2985984
129
        sage: hadamard_matrix(2)
130
        [ 1  1]
131
        [ 1 -1]
132
        sage: hadamard_matrix(8)
133
        [ 1  1  1  1  1  1  1  1]
134
        [ 1 -1  1 -1  1 -1  1 -1]
135
        [ 1  1 -1 -1  1  1 -1 -1]
136
        [ 1 -1 -1  1  1 -1 -1  1]
137
        [ 1  1  1  1 -1 -1 -1 -1]
138
        [ 1 -1  1 -1 -1  1 -1  1]
139
        [ 1  1 -1 -1 -1 -1  1  1]
140
        [ 1 -1 -1  1 -1  1  1 -1]
141
        sage: hadamard_matrix(8).det()==8^4
142
        True
143

144
    """
145
    if not(n%4==0) and not(n==2):
146
        raise ValueError, "The Hadamard matrix of order %s does not exist"%n
147
    if n==2:
148
        return matrix([[1,1],[1,-1]])
149
    if is_even(n):
150
        N = ZZ(n/2)
151
    elif n==1:
152
        return matrix([1])
153
    if is_prime(N-1) and (N-1)%4==1:
154
        return hadamard_matrix_paleyII(n)
155
    elif n==4 or n%8==0:
156
        had = hadamard_matrix(ZZ(n/2))
157
        chad1 = matrix([list(r)+list(r) for r in had.rows()])
158
        mhad = (-1)*had
159
        R = len(had.rows())
160
        chad2 = matrix([list(had.rows()[i])+list(mhad.rows()[i]) for i in range(R)]) 
161
        return chad1.stack(chad2)
162
    elif is_prime(N-1) and (N-1)%4==3:
163
        return hadamard_matrix_paleyI(n)
164
    else: 
165
        raise ValueError, "The Hadamard matrix of order %s is not yet implemented."%n
166

167
def hadamard_matrix_www(url_file, comments=False):
168
    """
169
    Pulls file from Sloanes database and returns the corresponding Hadamard
170
    matrix as a Sage matrix. You must input a filename of the form
171
    "had.n.xxx.txt" as described on the webpage 
172
    http://www.research.att.com/~njas/hadamard/, where "xxx" could be 
173
    empty or a number of some characters.
174

175
    If comments=True then the "Automorphism..." line of the had.n.xxx.txt 
176
    file is printed if it exists. Otherwise nothing is done.
177

178
    EXAMPLES::
179
        sage: hadamard_matrix_www("had.4.txt")             # requires internet, optional
180
        [ 1  1  1  1]
181
        [ 1 -1  1 -1]
182
        [ 1  1 -1 -1]
183
        [ 1 -1 -1  1]
184
        sage: hadamard_matrix_www("had.16.2.txt",comments=True)   # requires internet, optional
185
        Automorphism group has order = 49152 = 2^14 * 3
186
        [ 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1]
187
        [ 1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1]
188
        [ 1  1 -1 -1  1  1 -1 -1  1  1 -1 -1  1  1 -1 -1]
189
        [ 1 -1 -1  1  1 -1 -1  1  1 -1 -1  1  1 -1 -1  1]
190
        [ 1  1  1  1 -1 -1 -1 -1  1  1  1  1 -1 -1 -1 -1]
191
        [ 1 -1  1 -1 -1  1 -1  1  1 -1  1 -1 -1  1 -1  1]
192
        [ 1  1 -1 -1 -1 -1  1  1  1  1 -1 -1 -1 -1  1  1]
193
        [ 1 -1 -1  1 -1  1  1 -1  1 -1 -1  1 -1  1  1 -1]
194
        [ 1  1  1  1  1  1  1  1 -1 -1 -1 -1 -1 -1 -1 -1]
195
        [ 1  1  1  1 -1 -1 -1 -1 -1 -1 -1 -1  1  1  1  1]
196
        [ 1  1 -1 -1  1 -1  1 -1 -1 -1  1  1 -1  1 -1  1]
197
        [ 1  1 -1 -1 -1  1 -1  1 -1 -1  1  1  1 -1  1 -1]
198
        [ 1 -1  1 -1  1 -1 -1  1 -1  1 -1  1 -1  1  1 -1]
199
        [ 1 -1  1 -1 -1  1  1 -1 -1  1 -1  1  1 -1 -1  1]
200
        [ 1 -1 -1  1  1  1 -1 -1 -1  1  1 -1 -1 -1  1  1]
201
        [ 1 -1 -1  1 -1 -1  1  1 -1  1  1 -1  1  1 -1 -1]
202
    """
203
    n = eval(url_file.split(".")[1])
204
    rws = []
205
    url = "http://www.research.att.com/~njas/hadamard/"+url_file
206
    f = urllib.urlopen(url)
207
    s = f.readlines()
208
    for i in range(n):
209
        r = []
210
        for j in range(n):
211
            if s[i][j]=="+":
212
                r.append(1)
213
            else:
214
                r.append(-1)
215
        rws.append(r)
216
    f.close()
217
    if comments==True:
218
        lastline = s[-1]
219
        if lastline[0]=="A":
220
            print lastline
221
    return matrix(rws)
222

223
Product

Resources

Company
