#!/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()