2009 May « The Unapologetic Mathematician

Galois Connections

I want to mention a topic I thought I’d hit back when we talked about adjoint functors. We know that every poset is a category, with the elements as objects and a single arrow from $a$ to $b$ if $a\leq b$ . Functors between such categories are monotone functions, preserving the order. Contravariant functors are so-called “antitone” functions, which reverse the order, but the same abstract nonsense as usual tells us this is just a monotone function to the “opposite” poset with the order reversed.

So let’s consider an adjoint pair $F\dashv G$ of such functors. This means there is a natural isomorphism between $\hom(F(a),b)$ and $\hom(a,G(b))$ . But each of these hom-sets is either empty (if $a\not\leq b$ ) or a singleton (if $a\leq b$ ). So the adjunction between $F$ and $G$ means that $F(a)\leq b$ if and only if $a\leq G(b)$ . The analogous condition for an antitone adjoint pair is that $b\leq F(a)$ if and only if $a\leq G(b)$ .

There are some immediate consequences to having a Galois connection, which are connected to properties of adjoints. First off, we know that $a\leq G(F(a))$ and $F(G(b))\leq b$ . This essentially expresses the unit and counit of the adjunction. For the antitone version, let’s show the analogous statement more directly: we know that $F(a)\leq F(a)$ , so the adjoint condition says that $a\leq G(F(a))$ . Similarly, $b\leq F(G(b))$ . This second condition is backwards because we’re reversing the order on one of the posets.

Using the unit and the counit of an adjunction, we found a certain quasi-inverse relation between some natural transformations on functors. For our purposes, we observe that since $a\leq G(F(a))$ we have the special case $G(b)\leq G(F(G(b)))$ . But $F(G(b))\leq b$ , and $G$ preserves the order. Thus $G(F(G(b)))\leq G(b)$ . So $G(b)=G(F(G(b)))$ . Similarly, we find that $F(G(F(a)))=F(a)$ , which holds for both monotone and antitone Galois connections.

Chasing special cases further, we find that $G(F(G(F(a))))=G(F(a))$ , and that $F(G(F(G(b))))=F(G(b))$ for either kind of Galois connection. That is, $F\circ G$ and $G\circ F$ are idempotent functions. In general categories, the composition of two adjoint functors gives a monad, and this idempotence is just the analogue in our particular categories. In particular, these functions behave like closure operators, but for the fact that general posets don’t have joins or bottom elements to preserve in the third and fourth Kuratowski axioms.

And so elements left fixed by $G\circ F$ (or $F\circ G$ ) are called “closed” elements of the poset. The images of $F$ and $G$ consist of such closed elements

May 18, 2009 Posted by John Armstrong | Algebra, Category theory, Lattices | 6 Comments

DeMorgan’s Laws

And here’s the post I wrote today:

Today, I want to prove two equations that hold in any orthocomplemented lattice. They are the famous DeMorgan’s laws:

$\displaystyle\neg(x\vee y)=\neg x\wedge\neg y$
$\displaystyle\neg(x\wedge y)=\neg x\vee\neg y$

First, we note that $x\leq x\vee y$ by definition. Since our complementation reverses order, we find $\neg(x\vee y)\leq\neg x$ . Similarly, $\neg(x\vee y)\leq\neg y$ . And thus we conclude that $\neg(x\vee y)\leq\neg x\wedge\neg y$ .

On the other hand, $\neg x\wedge\neg y\leq\neg x$ by definition. Then we find $x=\neg\neg x\leq\neg(\neg x\wedge\neg y)$ by invoking the involutive property of our complement. Similarly, $y\leq\neg(\neg x\wedge\neg y)$ , and so $x\vee y\leq\neg(\neg x\wedge\neg y)$ . And thus we conclude $\neg x\wedge\neg y\leq\neg(x\vee y)$ . Putting this together with the other inequality, we get the first of DeMorgan’s laws.

To get the other, just invoke the first law on the objects $\neg x$ and $\neg y$ . We find

$\displaystyle\begin{aligned}\neg x\vee\neg y&=\neg\neg(\neg x\vee\neg y)\\&=\neg(\neg\neg x\wedge\neg\neg y)\\&=\neg(x\wedge y)\end{aligned}$

Similarly, the first of DeMorgan’s laws follows from the second.

Interestingly, DeMorgan’s laws aren’t just a consequence of order-reversal. It turns out that they’re equivalent to order-reversal. Now if $x\leq y$ then $x=x\wedge y$ . So $\neg x=\neg(x\wedge y)=\neg x\vee\neg y$ . And thus $\neg y\leq\neg x$ .

May 8, 2009 Posted by John Armstrong | Algebra, Lattices | 8 Comments

Upper-Triangular Matrices and Orthonormal Bases

I just noticed in my drafts this post which I’d written last Friday never went up.

Let’s say we have a real or complex vector space $V$ of finite dimension $d$ with an inner product, and let $T:V\rightarrow V$ be a linear map from $V$ to itself. Further, let $\left\{v_i\right\}_{i=1}^d$ be a basis with respect to which the matrix of $T$ is upper-triangular. It turns out that we can also find an orthonormal basis which also gives us an upper-triangular matrix. And of course, we’ll use Gram-Schmidt to do it.

What it rests on is that an upper-triangular matrix means we have a nested sequence of invariant subspaces. If we define $U_k$ to be the span of $\left\{v_i\right\}_{i=1}^k$ then clearly we have a chain

$\displaystyle U_1\subseteq\dots\subseteq U_{d-1}\subseteq U_d=V$

Further, the fact that the matrix of $T$ is upper-triangular means that $T(v_i)\in U_i$ . And so the whole subspace is invariant: $T(U_i)\subseteq U_i$ .

Now let’s apply Gram-Schmidt to the basis $\left\{v_i\right\}_{i=1}^d$ and get an orthonormal basis $\left\{e_i\right\}_{i=1}^d$ . As a bonus, the span of $\left\{e_i\right\}_{i=1}^k$ is the same as the span of $\left\{e_i\right\}_{i=1}^k$ , which is $U_k$ . So we have exactly the same chain of invariant subspaces, and the matrix of $T$ with respect to the new orthonormal basis is still upper-triangular.

In particular, since every complex linear transformation has an upper-triangular matrix with respect to some basis, there must exist an orthonormal basis giving an upper-triangular matrix. For real transformations, of course, it’s possible that there isn’t any upper-triangular matrix at all. It’s also worth pointing out here that there’s no guarantee that we can push forward and get an orthonormal Jordan basis.

May 8, 2009 Posted by John Armstrong | Algebra, Linear Algebra | 1 Comment

Orthogonal Complements and the Lattice of Subspaces

We know that the poset of subspaces of a vector space $V$ is a lattice. Now we can define complementary subspaces in a way that doesn’t depend on any choice of basis at all. So what does this look like in terms of the lattice?

First off, remember that the “meet” of two subspaces is their intersection, which is again a subspace. On the other hand their “join” is their sum as subspaces. But now we have a new operation called the “complement”. In general lattice-theory terms, a complement of an element $x$ in a bounded lattice $L$ (one that has a top element ${1}$ and a bottom element ${0}$ ) is an element $\neg x\in L$ so that $x\vee\neg x=1$ and $x\wedge\neg x=0$ .

In particular, since the top subspace is $V$ itself, and the bottom subspace is $\mathbf{0}$ we can see that the orthogonal complement $U^\perp$ satisfies these properties. The intersection $U\cap U^\perp$ is trivial, since the inner product is positive-definite as a bilinear form, and the sum $U+U^\perp$ is all of $V$ , as we’ve seen.

Even more is true. The orthogonal complement is involutive (when $V$ is finite-dimensional), and order-reversing, which makes it an “orthocomplement”. In lattice-theory terms, this means that $\neg\neg x=x$ , and that if $x\leq y$ then $\neg y\leq\neg x$ .

First, let’s say we’ve got two subspaces $U\subseteq W$ of $V$ . I say that $W^\perp\subseteq U^\perp$ . Indeed, if $p$ is a vector in $W^\perp$ then it $\langle w,p\rangle=0$ for all $w\in W$ . But since any $u\in U$ is also a vector in $W$ , we can see that $\langle u,p\rangle=0$ , and so $p\in U^\perp$ as well. Thus orthogonal complementation is

Now let’s take a single subspace $U$ of $V$ , and let $u$ be a vector in $U$ . If $v$ is any vector in $U^\perp$ , then $\langle v,u\rangle=\overline{\langle u,v\rangle}=0$ by the (conjugate) symmetry of the inner product and the definition of $U^\perp$ . Thus $u$ is a vector in $\left(U^\perp\right)^\perp$ , and so $U\subseteq U^{\perp\perp}$ . Note that this much holds whether $V$ is finite-dimensional or not.

On the other hand, if $V$ is finite-dimensional we can take an orthonormal basis $\left\{e_i\right\}_{i=1}^n$ of $U$ and expand it into an orthonormal basis $\left\{e_i\right\}_{i=1}^d$ of all of $V$ . Then the new vectors $\left\{e_i\right\}_{i=n+1}^d$ form a basis of $U^\perp$ , so that $V=U\oplus U^\perp$ . A vector in $V$ is orthogonal to every vector in $U^\perp$ exactly when it can be written using only the first $n$ basis vectors, and thus lies in $U$ . That is, $U^{\perp\perp}=U$ when $V$ is finite-dimensional.

May 7, 2009 Posted by John Armstrong | Algebra, Lattices, Linear Algebra | 7 Comments

The Category of Inner Product Spaces

So far we’ve been considering the category $\mathbf{Vect}$ of vector spaces (over either $\mathbb{R}$ or $\mathbb{C}$ ) and adding the structure of an inner product to some selected spaces. But of course there should be a category $\mathbf{Inn}$ of inner product spaces.

Clearly the objects should be inner product spaces, and the morphisms should be linear maps, but what sorts of linear maps? Let’s just follow our noses and say “those that preserve the inner product”. That is, a linear map $T:V\rightarrow W$ is a morphism of inner product spaces if and only if for any two vectors $v_1,v_2\in V$ we have

$\displaystyle\langle T(v_1),T(v_2)\rangle_W=\langle v_1,v_2\rangle_V$

where the subscripts denote which inner product we’re using at each point.

Of course, given any inner product space we can “forget” the inner product and get the underlying vector space. This is a forgetful functor, and the usual abstract nonsense can be used to show that it creates limits. And from there it’s straightforward to check that the category of inner product spaces inherits some nice properties from the category of vector spaces.

Most of the structures we get this way are pretty straightforward — just do the same constructions on the underlying vector spaces. But one in particular that we should take a close look at is the biproduct. What is the direct sum $V\oplus W$ of two inner product spaces? The underlying vector space will be the direct sum of the underlying vector spaces of $V$ and $W$ , but what inner product should we use?

Well, if $v_1$ and $v_2$ are vectors in $V$ , then they get included into $V\oplus W$ . But the inclusions have to preserve the inner product between these two vectors, and so we must have

$\displaystyle\langle\iota_V(v_1),\iota_V(v_2)\rangle_{V\oplus W}=\langle v_1,v_2\rangle_V$

and similarly for any two vectors $w_1$ and $w_2$ in $W$ we must have

$\displaystyle\langle\iota_W(w_1),\iota_W(w_2)\rangle_{V\oplus W}=\langle w_1,w_2\rangle_W$

So the only remaining question is what do we do with one vector from each space? Now we use a projection from the biproduct, which must again preserve the inner product. It lets us calculate

$\displaystyle\langle\iota_V(v),\iota_W(w)\rangle_{V\oplus W}=\langle\pi_V(\iota_V(v)),\pi_V(\iota_W(w))\rangle_V=\langle v,0\rangle_V=0$

Thus the inner product between vectors from different subspaces must be zero. That is, distinct subspaces in a direct sum must be orthogonal. Incidentally, this shows that the direct sum between a subspace $U\subseteq V$ and its orthogonal complement $U^\perp$ is also a direct sum of inner product spaces.

May 6, 2009 Posted by John Armstrong | Algebra, Linear Algebra | 6 Comments

Orthogonal Complements

An important fact about the category of vector spaces is that all exact sequences split. That is, if we have a short exact sequence

$\displaystyle\mathbf{0}\rightarrow U\rightarrow V\rightarrow W\rightarrow\mathbf{0}$

we can find a linear map from $W$ to $V$ which lets us view it as a subspace of $V$ , and we can write $V\cong U\oplus W$ . When we have an inner product around and $V$ is finite-dimensional, we can do this canonically.

What we’ll do is define the orthogonal complement of $U\subseteq V$ to be the vector space

$\displaystyle U^\perp=\left\{v\in V\vert\forall u\in U,\langle u,v\rangle=0\right\}$

That is, $U^\perp$ consists of all vectors in $V$ perpendicular to every vector in $U$ .

First, we should check that this is indeed a subspace. If we have vectors $v,w\in U^\perp$ , scalars $a,b$ , and a vector $u\in U$ , then we can check

$\displaystyle\langle u,av+bw\rangle=a\langle u,v\rangle+b\langle u,w\rangle=0$

and thus the linear combination $av+bw$ is also in $U^\perp$ .

Now to see that $U\oplus U^\perp\cong V$ , take an orthonormal basis $\left\{e_i\right\}_{i=1}^n$ for $U\subseteq V$ . Then we can expand it to an orthonormal basis $\left\{e_i\right\}_{i=1}^d$ of $V$ . But now I say that $\left\{e_i\right\}_{i=n+1}^d$ is a basis for $U^\perp$ . Clearly they’re linearly independent, so we just have to verify that their span is exactly $U^\perp$ .

First, we can check that $e_k\in U^\perp$ for any $k$ between $n+1$ and $d$ , and so their span is contained in $U^\perp$ . Indeed, if $u=u^ie_i$ is a vector in $U$ , then we can calculate the inner product

$\displaystyle\langle u^ie_i,e_k\rangle=\bar{u^i}\langle e_i,e_k\rangle=\bar{u^i}\delta_{ik}=0$

since $i\leq n$ and $k\geq n+1$ . Of course, we omit the conjugation when working over $\mathbb{R}$ .

Now, let’s say we have a vector $v\in U^\perp\subseteq V$ . We can write it in terms of the full basis $\left\{e_k\right\}_{k=1}^d$ as $v^ke_k$ . Then we can calculate its inner product with each of the basis vectors of $U$ as

$\displaystyle\langle e_i,v^ke_k\rangle=v^k\langle e_i,e_k\rangle=v^k\delta_{ik}=v^i$

Since this must be zero, we find that the coefficient $v^i$ of $e_i$ must be zero for all $i$ between ${1}$ and $n$ . That is, $U^\perp$ is contained within the span of $\left\{e_i\right\}_{i=n+1}^d$

So between a basis for $U$ and a basis for $U^\perp$ we have a basis for $V$ with no overlap, we can write any vector $v\in V$ uniquely as the sum of one vector from $U$ and one from $U^\perp$ , and so we have a direct sum decomposition as desired.

May 4, 2009 Posted by John Armstrong | Algebra, Linear Algebra | 12 Comments

Next Entries »

About this weblog

This is mainly an expository blath, with occasional high-level excursions, humorous observations, rants, and musings. The main-line exposition should be accessible to the “Generally Interested Lay Audience”, as long as you trace the links back towards the basics. Check the sidebar for specific topics (under “Categories”).

I’m in the process of tweaking some aspects of the site to make it easier to refer back to older topics, so try to make the best of it for now.

RSS Feeds

RSS - Posts
RSS - Comments
Feedback

Got something to say? Anonymous questions, comments, and suggestions at Formspring.me!
Subjects
Archives

May 2009

M T W T F S S

« Apr Jun »

1 2 3

4 5 6 7 8 9 10

11 12 13 14 15 16 17

18 19 20 21 22 23 24

25 26 27 28 29 30 31
Search for:

The Unapologetic Mathematician

Mathematics for the interested outsider

Galois Connections

DeMorgan’s Laws

Upper-Triangular Matrices and Orthonormal Bases

Orthogonal Complements and the Lattice of Subspaces

The Category of Inner Product Spaces

Orthogonal Complements

About this weblog

Recent Posts

Blogroll

Art

Astronomy

Computer Science

Education

Mathematics

Me

Philosophy

Physics

Politics

Science

RSS Feeds

Feedback

Subjects

Archives

Site info

Follow “The Unapologetic Mathematician”

M	T	W	T	F	S	S
« Apr				Jun »
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31