Gramm-Schmidt

(see more in 02-decompositions)

Gramm-Schmidt is an -algorithm-;
the function it defines takes IN a set of vectors
  (linearly independent, else this algo breaks)
and spits OUT an orthonormal set
  that generates the same flag.

[This latter condition is the trickiest for kids to understand;
 casually, it's: ``The output set has something to do with the input
 set''.
 More simply, just do some examples and they'll get the picture.
 Properly, you should talk about flags. They are important.]

[BTW, throughout we don't need the set to be maximal,
 equiv, the flag to be complete;
 we do ask that the flag's dimensions just increase by 1 at each step
 though]

It corresponds to:
- a deformation retract of the (Stiefel) manifold of
  frames onto the orthonormal frames
[and thus also $\GL_n$ to $\OO_n$]
- an inverse to the map
  frames -> -oriented- flags
  (properly, it identifies -oriented- flags
   with orthonormal frames)

...and indeed QR factorization is properly:
``The frame manifold fibers over orthonormal frames,
  with fibre (a principal bundle for) a parabolic subgroup,
  and splits (via inclusion, duh)''

G-S gives the -unique- orthonormal frame for the -oriented- flag;
without the orientation condition, you could swap sign
(in the Hermetian case, you could multiply by anything on the unit
 circle);
this corresponds to the intersection of the orthogonal/unitary group
with the Borel group being the maximal torus of diagonal matrices with
unit norm entries, and you fix this by only allowing upper-triangular
with -positive- (real) diagonal entries.

Gramm-Schmidt is formally analogous to Gau\ss-Jordan:

In Gau\ss-Jordan, you row-reduce
IE, $RA=A'$ (equiv, $A=SA'$), where $R$ keeps track of the operations
(If you just do Gau\ss,
 you can further factor it as $PU$: do all the row swaps first,
 then just add vertically.
 Gau\ss-Jordan is about -solving equations nicely-;
 Gau\ss ian elimination has more math behind it though)

In Gramm-Schmidt, you orthonormalize a set of vectors.
Writing them as the columns of a matrix $M$, you get
$MP=Q$
(where $P$ is ``what apperations to do''),
or writing it on the other side,
$M=QR$
where $Q$ is (column) orthogonal ($Q^T Q = I$) and
$R$ is square upper-triangular
(with positive numbers on the diagonal)

See, in G-J you multiply on the -left- b/c it's row operations,
while in G-S you multiply on the -right- b/c it's column operations.
In both cases, you often just care about the output (RREF matrix,
orthonormal basis for flag), but you can keep track of the info for
the ride and see more structure.

    %    %    %    %    %    %    %    %

BTW, the process of G-S is:
Given the messy vectors $v_1,\dots,v_k$,
progressively -replace- 'em with nice vectors, say $u_1,\dots,u_k$
($u$ for ``unit'').
At each step:
1: make $v_i$ ortho to $u_j$, $j<i$
  (this is the tricky bit: the formula is
   $v_i \mapsto v_i - \left<v_i,u_j\right>u_j$
   it's just ``subtract enough $u_j$ to fix things'',
   and this is what takes ages)
2: fix the length
  (this is easy: divide by length)

For $v_1,v_2,v_3$, the process is:
$v_1$: -just fix length->
$v_2$: -perp to $u_1$-> -fix len->
$v_3$: -perp to $u_1$-> -perp to $u_2$-> -fix len->

Observations:
- making perp to $u_2$ does -not- mess up $u_1$
  (b/c you only modify by $u_2$, which is itself perp to $u_1$;
   this is a slightly tricky idea)
- actually, the perping commutes!
[You can also see this at the level of the transvections that these
correspond to]

A way to describe why to make perp, you change by dot
  product/projection
  [Firstly, this is obvious if you just look at the frickin' picture]
[likewise for why perp means exactly "projection is zero"]
Imagine that the sun is directly overhead,
  and that there's a stick in the ground.
  The stick is vertical iff it "casts no shadow"
  (see? shadow = dot product = projection, roughly)
  ...and the -length- of the shadow reflects how far off-vertical it
  is, and how much you need to shift it by to -make- it vertical.
[Beware that this is confusing, as a stick doesn't get -sheared-,
 but gets -rotated-. Approximately same thing.]

BTW, G-S is partly useful and interesting in itself,
but is mostly there to cement in the notion of dot product.

    %    %    %    %    %    %    %    %

BTW, what's the deal with flags?
Basically:
given a -set- of vectors, the natural thing is to take their -span-.
If the set is -ordered-, you can also take the partial spans, and get
the -flag-: an ordered set -spans a flag-.
So flags are an ``ordered analog'' for subspaces
(they're more than just that, obviously)
