\section{Bases and coordinates}
%\section{Duals in Coordinates, and Change of Base}
This section is somewhat long and technical: I explain essentially everything
about bases and coordinates in linear algebra.

Note that a very good concrete space to work with when you want a
concrete space but not a specified basis is the space of polynomials.
In particular, there's lots of ways of describing elements of the
dual \emph{without} using coordinates. It's a very good alternative to
$K^n$, which has a confusing basis, and $V$, which is just abstract.


It's often useful for intuition and concreteness to work things out in
terms of a basis. However, you should also be cautious about bases as
they obscure the theory and the actual structure: if you can do
something in terms of a basis, doing it without choosing a basis will
generally clarify matters and deepen your understanding.

The most important theoretical task when doing a construction in terms
of a basis is to ask what happens when we \emph{change} the basis.
Why does this matter so much?
Because if we do something in terms of a basis, and know what happens
when we change the basis, then we know the whole story
\emph{independent} of choice of basis.

\subsection{Notation}
We potentially have a great many bases at once:
to understand all the possibilities, we'll want to understand two
spaces, $V$ and $W$, and maybe two bases on each, and for any basis
we also have a dual basis on $V^*$, so we could get $8$ bases!
It's easy to get confused.

Further, the ``correct'' mathematical notation can obscure matters
further: one often denote the basis $\seq{e_1,\dots,e_n}$ by
$\cB_e$ or some such, which is pretty verbose.

There's lots of conventions, especially for duals.

One might use $e_1,\dots,e_n$ as a basis for $V$,
and $f_1,\dots,f_m$ as a basis for $W$.

Or $e_1,\dots,e_n$ as a basis for $V$,
and $f_1,\dots,f_n$ as \emph{another} basis for $V$.

Or $e_1,\dots,e_n$ as a basis for $V$,
and $e'_1,\dots,e'_n$ as \emph{another} basis for $V$.

For duals, one might use
$e_i$ as a basis for $V$,
and $e'_i$ (or $e^*_i$, or $f_i$, or $f^i$)
as the dual basis for $V^*$

FIXME: be consistent below!

Lastly, I use $\phi$ and $\psi$ for the coordinates maps in analogy
with manifolds, where we use these for coordinate patches.

\subsection{Categorical background}
The key to understanding the relationship between (abstract) linear
algebra and (coordinate) matrix algebra is:

``$\bR^n$ and matrices are a skeletal subcategory of vector spaces and
linear maps''

Given a category $C$, a \Def{skeletal subcategory} $S$ is specified by
a collection of objects $\set{A_i}$ (called the \Def{skeleton}), with
exactly one from each isomorphism class of $C$.
IE, for all object $X \in C$, there is a
unique $A_i$ such that $X \cong A_i$. We let $S$ be the \Def{full
subcategory} on $\set{A_i}$: that is, the objects are the $\set{A_i}$,
and the maps are \emph{all} maps\footnote{In the notion of a
subcategory, we also want to allow ourselves to throw out maps.
So for instance the category of vector spaces and injective linear
maps is a subcategory of vector spaces and all linear maps} between them.

[Formally: the inclusion of a skeletal subcategory has as
adjoint: ``send an object to the element of the skeleton that it's
isomorphic to''. This doesn't specify an adjunction: it's not just two
functors, but -also- requires a consistent -identification- of the two
Hom-sets. We can provide this by specifying isomorphisms
$\phi_X\from A_i \isoto X$ for all objects; this is the unit of the
adjunction, and this is a good example of how two functors and a unit
determine an adjunction.

That is, a skeletal subcategory is reflective (and coreflective), and
the isomorphisms are the (co)reflection.]

Given a skeletal subcategory, you can ``reduce most questions'' to
questions inside the skeleton. This statement is intentionally vague:
it's rather like ``first-order logic'': any statement about a specific
diagram can be so reduced, but questions about the category as a whole
can't be reduced: see below under ``Limitations of skeletons''.

How does this work?

Given an object $X\in C$, we have $\phi_X\from A_i \to X$, so any
question about the object $X$ can be answered by answering the
(transfered) question about its isomorphic object $A_i$.
EG, the space of (orthonormal) $1$-frames in $\bR^n$ is (naturally)
homeomorphic to $S^{n-1}$, so the space of $1$-frames in any real
vector space $V$ of dimension $n$ is homeomorphic to $S^{n-1}$.

Now given two objects $X, Y\in C$, with $\phi_X \from A_i \to X$
and $\phi_Y\from A_j \to Y$, we have 
$$(\phi_X^{-1}\times \phi_Y)_* \from \Hom(A_i,A_j) \isoto \Hom(X,Y)$$
so any question about the $\Hom$-object can be reduced to within the
skeleton.

For instance, every linear map between finite-dimensional
vector spaces has a rank, by defining the rank of a matrix and
representing the linear map as a matrix.
We can also prove this directly though, and this is a good example of
how intrinsic definitions offer more insight.

Similarly any other diagram can be reduced into the skeleton.

A caution: note that we also have $\End X \cong \End A_i$ by
$$(\phi_X^{-1}\times \phi_X)_* \from \Hom(A_i,A_i) \isoto \Hom(X,X)$$
but that we need to use the same identification each time.

Lastly, note that isomorphisms between two objects can be identified
with automorphism of a fixed object:
$$\Iso(X,Y) \cong \Aut(A_i)$$
if $A_i \cong X \cong Y$. Note that $\Iso(X,Y)$ is a torsor (for
$\Iso(Y)$ and for $\Iso(X)^\op$), and $\Aut(A_i)$ is a group (recall
that a group is exactly a pointed torsor): the point comes from the
isomorphism $\phi_Y \phi_X^{-1}:X \to A_i \to Y$.

\subsection{Matrices as a skeletal subcategory for linear maps}
We now work out what this abstraction means for the specific case of
linear algebra.

So for vector spaces and linear maps, every vector space $V$ is isomorphic
to $\bR^n$ for some $n$: in fact, for $n=\dim V$.

Similarly, $\Hom(V,W)$ is isomorphic to $\Mat(m,n)$ ($m\times n$
matrices, IE, $m$ rows and $n$ columns), where $n=\dim V, m=\dim W$
(note the reversal: rows is output, columns is input),
via $\bR^n \cong V$ and $\bR^m \cong W$, and maps
$\bR^n \to \bR^m$ have natural matrix representations.

A choice of isomorphism $\bR^n \isoto V$ is \emph{exactly} the same as
a choice of basis.
The correspondence is given by:
\begin{itemize}
 \item given a basis $e_1,\dots,e_n$, we get a map $\bR^n \to V$
  by $(a_1,\dots,a_n)\in \bR^n \mapsto a_1e_1+\dots+a_ne_n \in V$.
  This is an isomorphism by definition of basis.
 \item given an isomorphism $\phi\from \bR^n \isoto V$,
 we get a basis $e_1,\dots,e_n$ of $V$ by $e_1=\phi(1,0,\dots,0)$,
 $e_2=\phi(0,1,0,dots,0)$, etc. -- just push the standard basis
 forward. This is a basis by definition of isomorphism.
\end{itemize}

Okay, so given a map $T\from V \to W$, how do we express it in terms
of a basis, from this point of view?
A basis $e_1,\dots,e_n$ of $V$ corresponds to $\phi_e\from \bR^n
\isoto V$, and a basis $f_1,\dots,f_m$ of $W$ corresponds to
$\psi_f \from \bR^m \isoto W$.

So we get a diagram
$$\xymatrix{\bR^n \ar[d]_{\phi_e} & \bR^m\ar[d]^{\psi_f}\\
 V\ar[r]^T & W}$$
and to get a matrix we need a map $M\from \bR^n \to \bR^m$, IE, we need a map
$$\xymatrix{\bR^n \ar[d]_{\phi_e}\ar@{-->}[r]^M & \bR^m\ar[d]^{\psi_f}\\
 V\ar[r]^T & W}$$
``such that the diagram commutes'', IE it doesn't matter which path
you follow: the result is the same -- this requirement just means that
$M$ represents $T$: it's not some arbitrary map.

This is easy to get: it's
$$M=\psi_f^{-1}T\phi_e$$
just reverse $\psi_f$!
This formula tells us a lot: see how changing the basis of the domain
acts on the right, while changing the basis of the codomain acts on
the left -- but with an inverse. Each of these is reflected in the
nuances of the computations.

Also, note that it says ``our input is in terms of the basis $e$; our
output is in terms of the basis $f$'': input comes in on the right and
comes out on the left. Yes, this is confusing: it's because we want to
write $T(x)$ (we want to write $T$ on the left), which means the $x$
comes in the right side of $T$ and comes out the left: think of
$U(T(x))$. In some places they do composition and matrix
multiplication the other way: $(x)T$ and $((x)T)U$.
(This especially makes sense in languages that put the verb last, like
Deutsch, I think; our $f(x)$ comes from putting the verb before the
object.)

Now write $T$ in terms of other bases, $e'$ and $f'$, getting $M'$;
clearly $M'=\psi_{f'}^{-1}T\phi_{e'}$
How can we get $M'$ from $M$?
Let's look at fixing the base on $V$:
algebraically,
we need to multiply $M$ on the right by
$B_{e'\to e}=\phi_e^{-1}\phi_{e'}$.

How can we interpret this?
$B_{e'\to e}$ is the \emph{identity} on $V$, with input written in
basis $e'$, and output written $e$.

Note that this is just a map $\bR^n \to \bR^n$: we cannot interpret it
as a map $T\from V \to V$, written in some basis $\seq{g_i}$, because
it would have to be of the form: $\phi_g^{-1}T\phi_g$.

However, what makes this confusing is that \emph{this very matrix}
admits two more interpretations, if we interpret it as a map $V \to V$
in the basis $\seq{e_i}$ or $\seq{e'_i}$:

In the basis $\seq{e_i}$, we get:
$$B_{e'\to e}=\phi_e^{-1}\phi_{e'}=\phi_e^{-1}\phi_{e'}\phi_e^{-1}\phi_e$$
In the basis $\seq{e'_i}$, we get:
$$B_{e'\to e}=\phi_e^{-1}\phi_{e'}=\phi_{e'}^{-1}\phi_{e'}\phi_e^{-1}\phi_{e'}$$
IE, the map $T_{e \to e'}\from V\to V$, where
$T=\phi_{e'}\phi_e^{-1}$, such that $T(e_i)=e'_i$ (it sends $e_i$ to
the $i$th basis vector of $\bR^n$, which it sends to $e'_i$)

FIXME: ack!!!!!
Okay, so this matrix tells you how to rewrite coordinates for $e'$
as coordinates for $e$, but it represents (in both the basis $e$ and
the basis $e'$???) the map that sends $e \to e'$???


We work this out in much, much more detail below.

\subsection{Dual of a basis}
One interpretation of duals are as ``coordinates''.

More correctly: ``a element of $V^*$ is a coordinate on $V$,
and a basis for $V^*$ is a system of coordinates on $V$''

Given a basis $e_1,\dots,e_n$ of $V$, we get a \Def{dual basis}
$f_1,\dots,f_n$ of $V^*$, given by:\\
``$f_i(v)$ is the coefficient of $e_i$ when you express $v$ in terms
of the basis $e_1,\dots,e_n$''

In symbols, if $v=a_1e_1+\dots+a_ne_n$ (where $a_i\in K$), then
$f_i(v)=a_i$.

Note that each $f_i$ depends on the \emph{entire} basis
$e_1,\dots,e_n$:\\
``you can't take the dual of a vector -- only the dual of a basis''

More formally,  if you change a basis, leaving one vector fixed, the
dual change of the dual basis needn't leave the dual vector fixed.

This will be clearer when we discuss the effect of change of basis on
the dual.

This point is particularly important in differential geometry:
$dx_i$ is canonical, but $\partial/\partial x_i$ isn't (it depends on
the whole basis -- IE, it's kinda bad notation)

\subsection{Duals in coordinates}

NB: dual map is transpose

\subsection{Change of basis on a vector space}
Given two bases $e_1,\dots,e_n$ and $f_1,\dots,f_n$ for a vector
space $V$, we can ask how to switch between the two.

That, if $v=a_1e_1+\dots+a_ne_n=b_1f_1+\dots+b_nf_n$, then how can we
express $\seq{b_i}$ in terms of $\seq{a_i}$? This is a question about
the \emph{dual} space, IE, it's about coordinates, so we will demur.
You'll thank me for this -- this can get pretty confusing, with all
the back and forth.

FIXME:
Let's first write the matrix $M_{e\to f; e}$; that is, the matrix that
takes $\seq{e_i}$ to $\seq{f_i}$, expressed in the basis
$\seq{e_i}$. That is, $T_{e \to f}$, the linear transform of $V$
defined by $T(e_i) = f_i$ is well-defined; we're just writing it in a
basis.


\subsection{Classification of maps $V \to W$}
We will illustrate change of basis by recalling a classification theorem,
and showing the analog for duals.

\begin{thm}
Recall that maps $V \to W$ are ``classified'' by their rank.
In coordinates, this says that if $T\from V \to W$ has rank $k$, then there
are bases for $V$ and $W$ such that the matrix for $T$ has the form
like:
$$\begin{pmatrix}
1 & 0 & \\
0 & 1 & 0 & \\
  & 0 & 1 & 0 & \\
  &   & 0 & 0 & 0
 \end{pmatrix}$$
IE, it has $k$ `$1$'s on the diagonal, followed by `$0$'s on the
diagonal, and `$0$'s everywhere else.
\end{thm}
\begin{proof}
The proof is by row and column reduction. That is, if $\dim V = n$ and
$\dim W = m$, then a choice of basis for $T$ expresses it as an
$m\times n$ matrix: $m$ rows (because that's the output), and $n$
columns (because that's the input).

mneumonic for left and right:
left action is by row operations; right action is by column operations
left action act on column vectors;
given a set of vectors, it acts on each column in the same way
in particular, it doesn't change the columns around,
hence it must be acting by row operations
dually for a right action

intrinsically defined
\end{proof}

A better formulation of the above result is:
\begin{defn}
Say that two diagrams $T\from V \to W$ and $T'\from V' \to W'$ are
\Def{equivalent} if there are isomorphisms $\phi\from V \isoto V'$
and $\psi\from W \to W'$ such that this diagram commutes:
$$\xymatrix{V \ar[r]^T\ar[d]_\phi & W\ar[d]_\psi\\
V'\ar[r]^{T'} & W'}$$

Even more formally, consider the category of functors
$$(\cdot \to \cdot) \to \Vect$$
where objects are functors between these categories and morphisms are
natural transforms of functors.
This is called the \Def{quiver category}, because it's a bunch of
arrows.

Concretely, an object is just ``put a vector space at each dot, and a
map on each arrow'', and a map is ``maps between the corresponding
objects such that everything commutes''.

Then two diagrams are equivalent if and only if they are isomorphic in
the quiver category.
\end{defn}


first do for two separate spaces, then for one space
(Jordan is harder)
(now that I have language of quivers, life is good)

%--------------------
\section{Vectors, Covectors and Transposes}


(cute way of visualizing the duality: horizontal vectors and
 vertical vectors. Note that this requires a basis
 cute: this is actually identifying $V = Hom(K,V)$
 and $V^* = Hom(V,K)$ -- that's what the matrices mean)
(transposes as making sense once you have a basis)
(note that adjoints always make sense, even for square matrices!)

(note that you can always glue on a one-dimensional vector space ;-)

with this, you can deal with functors, but not with such things as
$V \oplus V^*$

also: get bases for symmetric power, alt power, and even other schur
functors!

\subsection{Quadratic forms as matrices}
Lastly, note that quadratic forms can be represented as matrices, but
the change of basis rule differs (physicists say: ``they transform
differently''): you conjugate $M \mapsto A^TMA$, rather than
$A^{-1}MA$, as you do for endomorphisms.
As a result, the classification is completely different.
Rather than Jordan form, over an algebraically closed field the only
invariant is rank (er, $\dim$ minus max isotropic $\dim$ (is this word
for ``space on which restricts to $0$''?).
Over the reals, you get signature (aka, index: see Sylvester's
theorem). Over $\bQ$ and $\bZ$, life is much more interesting.

Note in particular that our usual invariants of matrices, like trace
and determinant and all, are not invariant -- though if $A^T=A^{-1}$,
then conjugation by $A$ doesn't change 'em.
Hence the characteristic poly etc. reflects the \emph{metric
properties} of our basis, or rather of the quadratic form w/r/t that
basis.

These are pretty easy to understand:
the determinant is the square of the (absolute value of the) volume of the basis,
w/r/t the form (IE, the form defines a length, so the parallelepiped defined by
the basis has a volume). Proof is immediate: if it's an inner product,
then $M=A^* I A$, so $\det M = \det A^* \det A=(\det A)^* \det A$.

Similarly, the trace is the sum of the (absolute values of the squares
of) norms of the basis. For the other symmetric polys, it's similar:
sum of the (abs val of squares of the) areas of the squares determined
by pairs of basis vectors, etc.

Note that this is kinda goofy if your form is indefinite; also, I'm
not sure how to interpret minimal polynomial, or directly interpret
the characteristic poly.

\subsection{Limitations of skeletons}
%\subsection{Limitations of skeletons: $\cong \neq =$}
The following is rather picky, but matters in some contexts, and for
reasons of philosophy.

In a nutshell, % b/c it doesn't work in the subsection header
$\cong \neq =$.

It's not okay to just use $\bR^n$ and not use abstract vector spaces,
but the reason why is a bit subtle, and is categorical.
However, it should \emph{feel wrong} to think of $\bR^n$ and $(\bR^n)^*$ as
``the same space'' -- this is a good gauge of how comfortable you are
with duals. From the coordinates point of view, the former consists of
vectors, while the latter is covectors -- so for instance there's a
natural pairing of $V^*$ and $V$, but not of $V$ and $V$.
More sophisticated is that ${}^*$ is a contravarient functor, so
there's something weird here.

The difference is ultimately between $=$ and $\cong$: an isomorphism
is not the same thing as the identity.

concrete example: direct sum is ``not commutative on the nose''
(but is associative) (same issue for tensor product)


In topology this destinction between $=$ and $\cong$ (and ``homotopic
to'') is important: H-spaces, $A_\infty$, loop spaces, etc.

-----------------------------------------------------------
quadratic forms, symmetric, etc.
maps preserving a basis are lame;
basis gives inner product
different bases give same inner product
  ...fibres are an O(n) foliation of GL(n)
  ...and get O(n) as subgroup preserving an inner product
  a choice of basis gives $S_n < O(n)$
  (heh: a clever student might ask: does every $S_n < O(n)$
   correspond to a basis? This is a very good question:
   it leads to representation theory, IE, how can groups (of
   symmetries) be realized as linear symmetries, IE symmetries of
   a vector space. Oh, and the answer is no -- there's lots of other
   interesting ways to realize $S_n$ as a subgroup of $O(n)$,
   and the connection between $S_n$ and $O(n)$ is very deep indeed;
   the ``best answer'' so far is called ``Springer theory''.)
affine spaces: space of frames, etc.
-----------------------------------------------------------
BTW, here's another example, which also clarifies duals generally:
Looking at $\bR^2$,
$(1,0), (0,1)$ is the natural basis for it,
and the corresponding dual basis for $\left(\bR^2\right)^*$
is $x,y$
