Ask Your Question
2

Determinants over cyclotomic fields are broken?

asked 2022-09-27 09:36:54 +0200

Alex Karenin gravatar image

updated 2023-01-09 23:59:56 +0200

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.

edit retag flag offensive close merge delete

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 ( 2022-09-27 12:58:19 +0200 )edit

try starting with copies of the identity matrices

FrédéricC gravatar imageFrédéricC ( 2022-09-28 09:47:11 +0200 )edit

2 Answers

Sort by » oldest newest most voted
1

answered 2022-09-27 15:48:07 +0200

FrédéricC gravatar image

updated 2022-09-27 15:50:03 +0200

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 !?

edit flag offensive delete link more

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 ( 2022-09-28 07:30:54 +0200 )edit
2

answered 2022-09-28 14:39:43 +0200

updated 2022-09-28 15:23:57 +0200

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. :-(

edit flag offensive delete link more

Comments

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

Dima gravatar imageDima ( 2022-09-28 18:15:58 +0200 )edit

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: 2022-09-27 09:36:54 +0200

Seen: 180 times

Last updated: Sep 28 '22