# The Unapologetic Mathematician

## 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