The Unapologetic Mathematician

Mathematics for the interested outsider

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 | 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 | Algebra, Linear Algebra | 1 Comment

   

Follow

Get every new post delivered to your Inbox.

Join 216 other followers