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

First, we note that by definition. Since our complementation reverses order, we find . Similarly, . And thus we conclude that .

On the other hand, by definition. Then we find by invoking the involutive property of our complement. Similarly, , and so . And thus we conclude . 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 and . We find

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 then . So . And thus .

## 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 of finite dimension with an inner product, and let be a linear map from to itself. Further, let be a basis with respect to which the matrix of 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 to be the span of then clearly we have a chain

Further, the fact that the matrix of is upper-triangular means that . And so the whole subspace is invariant: .

Now let’s apply Gram-Schmidt to the basis and get an orthonormal basis . As a bonus, the span of is the same as the span of , which is . So we have exactly the same chain of invariant subspaces, and the matrix of 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.