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

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.

Posted by John Armstrong | Algebra, Linear Algebra | 1 Comment

## 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 36, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8916230201721191, "perplexity_flag": "head"}