1.py

from math import sqrt, pow

print_matrix = lambda matrix: reduce(lambda y, x: y + "\n" + " ".join(map(lambda z: str(z), x)), matrix, "")
print_vector = lambda vector: reduce(lambda y, x: y + "\n" + str(x), vector, "")
print_vector_inline = lambda vector: reduce(lambda y, x: y + str(x) + " ", vector, "")
copy_matrix = lambda m: map(lambda x: map(lambda y: y, x), m)


def read(filename):
    matrix = []
    with open(filename) as f:
        for i, val in enumerate(f):
            row = map(lambda value: float(value), val.split(" "))
            matrix.append(row)
    return matrix


def multiplication_matrix(first_matrix, second_matrix):
    result = []
    for i in range(len(first_matrix)):
        row = [0]*len(first_matrix)
        for j in range(len(second_matrix)):
            for k in range(len(first_matrix)):
                row[j] += first_matrix[i][k] * second_matrix[k][j]
        result.append(row)
    return result


def multiplication_matrix_on_vector(matrix, vector):
    res = [0] * len(matrix)
    for i in range(len(matrix)):
        res[i] = 0
        for j in range(len(matrix[0])):
            res[i] += matrix[i][j]*vector[j]
    return res


def subtract_vector(first_vector, second_vector):
    res = [0] * len(first_vector)
    for i in range(len(first_vector)):
        res[i] = first_vector[i] - second_vector[i]
    return res


def create_b_matrix(matrix, cur, flag):
    result = []
    for i in range(len(matrix)):
        row = [0] * i + [1] + [0]*(len(matrix) - i - 1)
        for j in range(len(matrix)):
            if i != cur: continue
            index = i + 1
            row[j] = matrix[index][j] if flag else 1 / matrix[index][i] if j == i else -1 * matrix[index][j] / matrix[index][i]
        result.append(row)

    return result


def normalize(matrix):
    b_matrix_res = []

    for i in range(len(matrix)-1):
        index = len(matrix) - i - 2

        b_matrix_transpose = create_b_matrix(copy_matrix(matrix), index, True)
        b_matrix = create_b_matrix(copy_matrix(matrix), index, False)
        b_matrix_res = multiplication_matrix(b_matrix_res, b_matrix) if len(b_matrix_res) else b_matrix
        matrix = multiplication_matrix(b_matrix_transpose, matrix)
        matrix = multiplication_matrix(matrix, b_matrix)

        print "\nB"+str(i+1)+"^-1:", print_matrix(b_matrix_transpose)
        print "\nB"+str(i+1)+":", print_matrix(b_matrix)
        print "\nA"+str(i+1)+":", print_matrix(matrix)

    return matrix, b_matrix_res


def print_equal(array):
    result = []
    for i in range(len(array)):
        index = len(array) - i - 1
        val = (str(array[i] * -1) if array[i] < 0 else "(-" + str(array[i]) + ")") + ("x^"+str(index) if index else " ")
        result.append(" + " + val if i else val)

    return "x^{0} + {1} = 0".format(len(array), reduce(lambda y, x: y + x, result, ""))


def get_y_matrix(vector):
    y_matrix = []
    for value in vector:
        cur = [1]
        for i in range(1, len(vector)):
            cur.append(value**i)
        y_matrix.append(cur[::-1])
    return y_matrix


def get_x_matrix(b_matrix, y_matrix):
    x_matrix = []
    for value in y_matrix:
        x_matrix.append(multiplication_matrix_on_vector(copy_matrix(b_matrix), list(value)))
    return x_matrix


def get_res_matrix(x_matrix):
    res_matrix = []
    for value in x_matrix:
        module = sqrt(reduce(lambda x, y: x+y, map(lambda x: x*x, value), 0))
        res_matrix.append(map(lambda x: x/module, value))
    return res_matrix


def get_vectors(vector, b_matrix):
    y_matrix = get_y_matrix(list(vector))
    x_matrix = get_x_matrix(copy_matrix(b_matrix), copy_matrix(y_matrix))
    print "\nY Matrix:", print_matrix(y_matrix)
    print "\nX Matrix:", print_matrix(x_matrix)
    return get_res_matrix(copy_matrix(x_matrix))


def check_results(vectors, eigenvalues, matrix):
    result_matrix = []
    for i in range(len(vectors)):
        res_matrix = multiplication_matrix_on_vector(copy_matrix(matrix), list(vectors[i]))
        res_vector = map(lambda x: x*eigenvalues[i], vectors[i])
        result_matrix.append(subtract_vector(res_matrix, res_vector))
    return result_matrix


def check_vector(some_vector, check_vector):
    sum = 0
    for i in range(len(some_vector)):
        sum += pow(some_vector[i] - check_vector[i], 2)
    return sqrt(sum/len(some_vector))


def check_vectors(vectors, check_equal_vectors):
    res_check = []
    for i in range(len(vectors)):
        res_check.append(check_vector(list(vectors[i]), list(check_equal_vectors[i])))
    return res_check


def main():
    filename = "input.txt"
    eigenvalues = [9.07909, 5.95438, 4.17598, 2.74654]
    check_equal_vectors = [
        [0.540203, 0.267716, 0.617617, 0.505033],
        [-0.79208, -0.123325, 0.349847, 0.484776],
        [0.254975, -0.573902, -0.477034, 0.614868],
        [-0.125613, 0.764039, -0.518261, 0.363141]
    ]

    matrix = read(filename)
    print "\nCondition:\n", print_matrix(matrix), "\n\nStart Calculation:"

    normalize_matrix, b_matrix = normalize(copy_matrix(matrix))
    print "\nNormal Form Matrix:", print_matrix(normalize_matrix), "\n\nB Matrix", print_matrix(b_matrix)

    print "\nEquation eigenvalues:", print_equal(normalize_matrix[0])
    print "\nEigenvalues:" + print_vector_inline(eigenvalues)

    vectors = get_vectors(list(eigenvalues), copy_matrix(b_matrix))
    print "\nVectors:", print_matrix(vectors)

    check_matrix = check_results(list(vectors), eigenvalues, matrix)
    print "\nCheck Vectors with Condition:", print_matrix(check_matrix)

    check_wolfram_vector = check_vectors(copy_matrix(vectors), copy_matrix(check_equal_vectors))
    print "\nCheck Vectors with Wolfram Alpha:", print_vector_inline(check_wolfram_vector)


main()