How to generate a cyclic matrix

edit

Here are some possibilities to generate a circulant matrix, having as input its first row a:

def circulantMatrix0( a ):
    n = len(a)
    R = range(n)
    return matrix( [ [ a[ (j-k) % n ] for j in R ] for k in R ] )

def circulantMatrix1( a ):
    n = len(a)
    R = range(n)
    return matrix( [ [ a[j-k] for j in R ] for k in R ] )

def circulantMatrix2( a, field=GF(2) ):
    n = len(a)
    T = matrix( F, n, n, [1 if k==(j+1)%n else 0
                          for j in range(n)
                          for k in range(n) ] )
    return sum( [ a[j]*T^j for j in range(n) ] )

def circulantMatrix3( a, field=GF(2) ):
    n = len(a)
    b = [a[j] for j in range(n)]
    b = b+b
    return matrix( n, n, [ b[n-j:2*n-j] for j in range(n) ] )


# Tests:

F = GF(2)
a = vector( F, 8, [1,0,0,0,1,0,0,1] )
A = circulantMatrix0(a)
B = circulantMatrix1(a)
C = circulantMatrix2(a)
D = circulantMatrix3(a)

Then we have:

sage: print A
[1 0 0 0 1 0 0 1]
[1 1 0 0 0 1 0 0]
[0 1 1 0 0 0 1 0]
[0 0 1 1 0 0 0 1]
[1 0 0 1 1 0 0 0]
[0 1 0 0 1 1 0 0]
[0 0 1 0 0 1 1 0]
[0 0 0 1 0 0 1 1]
sage: A==B and A==C and A==D
True
sage: A.charpoly().factor()
(x + 1)^8
sage: A.jordan_form()

[1 1 0 0 0 0 0 0]
[0 1 1 0 0 0 0 0]
[0 0 1 1 0 0 0 0]
[0 0 0 1 1 0 0 0]
[0 0 0 0 1 1 0 0]
[0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 0 1]
sage: