#!/usr/bin/python """Extract an orthonormal basis from a matrix, inefficiently. This is maybe not as interesting as I thought it was initially, since it's not clear what relationship the new orthonormal basis has to the original matrix, except that it spans the same subspace orthonormally; and it leaves any orthonormal prefix of the original matrix undisturbed. It's inefficient because it does O(N**3) work for an NxN matrix, and also because it's doing all the work in (presumably interpreted) Python. """ import sys import math class Vector: def __init__(self, contents): self.contents = contents def project_onto(self, other): # XXX why does this stop working when I replace # other.magnitude()**2 with other.dot(other)? return other.scaled_by(self.dot(other) / other.magnitude()**2) def magnitude(self): return math.sqrt(self.dot(self)) def scaled_by(self, c): return Vector([x * c for x in self.contents]) def dot(self, other): return sum(a*b for a, b in zip(self.contents, other.contents)) def __add__(self, other): return Vector([a+b for a, b in zip(self.contents, other.contents)]) def __sub__(self, other): return Vector([a-b for a, b in zip(self.contents, other.contents)]) def __str__(self): return ' '.join(str(x) for x in self.contents) def orthonormal_basis(input_rows): rows = [] for nums in input_rows: for row in rows: nums -= nums.project_onto(row) nums = nums.scaled_by(1/nums.magnitude()) rows.append(nums) yield nums def main(): rows = list(orthonormal_basis(Vector([int(field) for field in line.split()]) for line in sys.stdin)) for row in rows: print row print "dot products:" for a in rows: for b in rows: print a.dot(b), print if __name__ == '__main__': main()