"""Exact rational verification of the six Tiles constant-row pencils."""
from fractions import Fraction as F

def transpose(a):
    return [list(c) for c in zip(*a)]


def multiply(a, b):
    return [[sum(x * y for x, y in zip(row, col))
             for col in transpose(b)] for row in a]


def nullspace(a):
    a = [[F(x) for x in row] for row in a]
    n = len(a[0])
    pivots = []
    row = 0
    for col in range(n):
        pick = next((i for i in range(row, len(a)) if a[i][col]), None)
        if pick is None:
            continue
        a[row], a[pick] = a[pick], a[row]
        scale = a[row][col]
        a[row] = [x / scale for x in a[row]]
        for i in range(len(a)):
            if i != row:
                scale = a[i][col]
                a[i] = [x - scale * y for x, y in zip(a[i], a[row])]
        pivots.append(col)
        row += 1
        if row == len(a):
            break
    result = []
    for free in range(n):
        if free in pivots:
            continue
        vector = [F(0)] * n
        vector[free] = F(1)
        for i, col in enumerate(pivots):
            vector[col] = -a[i][free]
        result.append(vector)
    return result


coefficient_matrices = [
    [[1, 1, 0], [0, -2, 0], [0, 0, 0]],
    [[0, 0, 1], [0, -2, 1], [0, 0, 0]],
    [[0, 0, 0], [0, -2, 0], [0, 1, 1]],
    [[0, 0, 0], [1, -2, 0], [1, 0, 0]],
]
last_directions = [(1, -1, 0), (0, 0, 1), (0, 1, -1),
                   (1, 0, 0), (1, 1, 1), (-2, 1, -2)]
for lam in last_directions:
    evaluation = [[sum(coefficient_matrices[h][i][j] * lam[j]
                       for j in range(3)) for h in range(4)]
                  for i in range(3)]
    pencil = nullspace(evaluation)
    assert len(pencil) == 2
    matrices = [[[sum(v[h] * coefficient_matrices[h][i][j]
                      for h in range(4)) for j in range(3)]
                 for i in range(3)] for v in pencil]
    basis = transpose(nullspace([list(lam)]))
    gram = multiply(transpose(basis), basis)
    det = gram[0][0] * gram[1][1] - gram[0][1] * gram[1][0]
    inverse = [[gram[1][1] / det, -gram[0][1] / det],
               [-gram[1][0] / det, gram[0][0] / det]]
    coordinates = multiply(basis, inverse)
    compressed = [multiply(a, coordinates) for a in matrices]
    operators = [[compressed[i][rho][j] for i in range(2) for j in range(2)]
                 for rho in range(3)]
    annihilator = nullspace(operators)
    assert len(annihilator) == 1
    h = annihilator[0]
    determinant = h[0] * h[3] - h[1] * h[2]
    assert determinant != 0
    print('constant-row pencil', lam, 'annihilator', list(map(str, h)),
          'determinant', str(determinant))

print('All six constant-row pencil annihilators are invertible.')