sage: v = [v1,v2,v3]
sage: len(gram_schmidt(v)) == 2
True
- """
- if inner_product is None:
- inner_product = lambda x,y: x.inner_product(y)
- def norm(x):
- ip = inner_product(x,x)
- # Don't expand the given field; the inner-product's codomain
- # is already correct. For example QQ(2).sqrt() returns sqrt(2)
- # in SR, and that will give you weird errors about symbolics
- # when what's really going wrong is that you're trying to
- # orthonormalize in QQ.
- return ip.parent()(ip.sqrt())
-
- v = list(v) # make a copy, don't clobber the input
-
- # Drop all zero vectors before we start.
- v = [ v_i for v_i in v if not v_i.is_zero() ]
+ """
if len(v) == 0:
# cool
return v
- R = v[0].base_ring()
+ V = v[0].parent()
- # Our "zero" needs to belong to the right space for sum() to work.
- zero = v[0].parent().zero()
+ if inner_product is None:
+ inner_product = lambda x,y: x.inner_product(y)
sc = lambda x,a: a*x
- if hasattr(v[0], 'cartesian_factors'):
+ if hasattr(V, 'cartesian_factors'):
# Only use the slow implementation if necessary.
sc = _scale
def proj(x,y):
+ # project y onto the span of {x}
return sc(x, (inner_product(x,y)/inner_product(x,x)))
- # First orthogonalize...
- for i in range(1,len(v)):
- # Earlier vectors can be made into zero so we have to ignore them.
- v[i] -= sum( (proj(v[j],v[i])
- for j in range(i)
- if not v[j].is_zero() ),
- zero )
+ def normalize(x):
+ # Don't extend the given field with the necessary
+ # square roots. This will probably throw weird
+ # errors about the symbolic ring if you e.g. try
+ # to use it on a set of rational vectors that isn't
+ # already orthonormalized.
+ return sc(x, ~inner_product(x,x).sqrt())
- # And now drop all zero vectors again if they were "orthogonalized out."
- v = [ v_i for v_i in v if not v_i.is_zero() ]
+ v_out = [] # make a copy, don't clobber the input
- # Just normalize. If the algebra is missing the roots, we can't add
- # them here because then our subalgebra would have a bigger field
- # than the superalgebra.
- for i in range(len(v)):
- v[i] = sc(v[i], ~norm(v[i]))
+ for (i, v_i) in enumerate(v):
+ ortho_v_i = v_i - V.sum( proj(v_out[j],v_i) for j in range(i) )
+ if not ortho_v_i.is_zero():
+ v_out.append(normalize(ortho_v_i))
- return v
+ return v_out