Ask Your Question
2

Determinants over cyclotomic fields are broken?

asked 2 years ago

Alex Karenin gravatar image

updated 2 years ago

tmonteil gravatar image

I launch the code below which generates two unimodular matrices L and U until it thinks that norm(det(L*U)) is not in [-1,1] which is probably a bug:

def seek_bug(K,n, rng=[-3,3], density=1.0):
    print("Searching")
    z=K.gen()
    OK = K.fraction_field().ring_of_integers()

    units = [z^((1-(i))/2) * (1-z^i)/(1-z) for i in list( range(1,K.degree(),2) ) ] if K.degree()>2 else [1,z]   
    assert( all([OK(u).is_unit() for u in units]) ), "Wrong units!"

    L = Matrix.identity(K,n)
    U = Matrix.identity(K,n)
    for i in range(n):
        for j in range(n):
            if i<j:
                if uniform(0,1)<density:
                    L[i,j]=OK.random_element(rng[0],rng[1])
            elif j<i:
                if uniform(0,1)<density:
                    U[n-j-1,n-i-1]=OK.random_element(rng[0],rng[1])
            else:
                U[i,i]*=prod([ units[randrange(len(units))] for i in range(6) ])
                L[i,j]*=prod([ units[randrange(len(units))] for i in range(6) ])
    B = L*U
    if not( norm(det(B)) in [-1,1] ):
        return L, U, B
    return None, None, None

n=2
K.<z> = CyclotomicField(16)
L, U, B = None, None, None

while L is None:
    L, U, B = seek_bug(K,n)
print(norm(det(L)), norm(det(U)))
assert det(L)*det(U) == det(L*U), "This should work... But it doesn't"

The last assertion fails which implies det(L)det(U) != det(LU) (Note: even without taking the norm!), but this should not be the thing. It fails in power-of-two cyclotomics. Did I make a mistake, or are the determinants in sage are broken? Checked this on 3 machines with sage 9.4, 9.5 and 9.6: it fails everywhere.

Preview: (hide)

Comments

UPD: the code works as intended if I define matrices L and U over the ring of integers of the field K.

Alex Karenin gravatar imageAlex Karenin ( 2 years ago )

try starting with copies of the identity matrices

FrédéricC gravatar imageFrédéricC ( 2 years ago )

2 Answers

Sort by » oldest newest most voted
2

answered 2 years ago

updated 2 years ago

That's a bug, indeed. I opened https://trac.sagemath.org/ticket/34597

for matrices over cyclotomics a multi-modal algorithm is used, and it fails here. :-(

Preview: (hide)
link

Comments

I posted a branch which apparently fixes the problem, but I don't really know why.

Dima gravatar imageDima ( 2 years ago )
1

answered 2 years ago

FrédéricC gravatar image

updated 2 years ago

even a bug for diagonal matrices..

sage: K.<z> = CyclotomicField(16)
sage: L
[-575*z^7 - 439*z^6 - 237*z^5 + 237*z^3 + 439*z^2 + 575*z + 623                                                              0]
[                                                             0     -114*z^7 - 88*z^6 - 48*z^5 + 48*z^3 + 88*z^2 + 114*z + 123]
sage: U
[-1926*z^7 - 1474*z^6 - 798*z^5 + 798*z^3 + 1474*z^2 + 1926*z + 2085                                                                   0]
[                                                                  0   -1014*z^7 - 777*z^6 - 421*z^5 + 421*z^3 + 777*z^2 + 1014*z + 1097]
sage: det(L*U)==det(L)*det(U)
False

where the product LU is not diagonal !?

Preview: (hide)
link

Comments

Note that if you define

OK = K.ring_of_integers()    
L, U = matrix(OK,L), matrix(OK,U)

then it magically works. Also I found that the problem is rather in the matrix multiplication. If the matrices are over K then the following assertion fails:

LU = matrix( [ [L[i].inner_product(U.transpose()[j]) for j in range(2)] for i in range(2)] )
assert LU == L*U
Alex Karenin gravatar imageAlex Karenin ( 2 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2 years ago

Seen: 318 times

Last updated: Sep 28 '22