Monday, January 4, 2016

Cayley-Hamilton Theorem Part I: Norms

In this and a following blog post, I will explain and prove the Cayley-Hamilton theorem, a main algebraic result of linear operators. There are of course multiple proofs which can be found online, the vast majority of which approach it via algebraic means. My goal is to create an analytic proof to approach this problem.

In this post we deal exclusively with some facts about norms. These are common results which can be found in many textbooks.

Equivalence of norms

We first introduce the concept of a norm.
Let \(V\) be a vector space, and \(v_1,\,v_2\) be arbitrary elements of the space. A norm is a function \(f\colon V\to \mathbb{R}\) which satisfies the following three properites:
  1. \(f(v_1)\geq 0,\, f(v_1)=0\) if and only if \(v_1=\mathbf{0}\)
  2. \(af(v_1)=f(av_1)\)
  3. \(f(v_1+v_2)\leq f(v_1)+f(v_2)\).
The standard notation for the norm of a vector \(v\in V\) is \(\|v\|\).
We should note that a norm induces a metric given by \(d(v,u)=\|v-u\|\), and thus induces a topology on the vector space \(V\).
There are of course infinitely many norms we may use for any given vector space. It may be convenient to use different ones for different proofs. The following theorem will allow use any two interchangeably for most purposes.
Theorem: Let \(V\) be a finite-dimensional vector space and \(\|\cdot\|_1\) and \(\|\cdot\|_2\) be two norms on \(V\). Then there exists constants \(C_1,C_2\) with \(0\lt C_1\leq C_2\lt \infty\) such that for all \(\mathbf{v}\in V\) we have
$$C_1\|\mathbf{v}\|_2\leq \|\mathbf{v}\|_1\leq C_2\|\mathbf{v}\|_2.$$ We refer to this result as the equivalence of norms.
Proof: We first note that by the definition of two norms being equivalent, we merely need to show that one norm is equivalent to all others. We will define this norm as the following: Fix a basis of \(V\) given by \(\mathbf{e}_1,\cdots,\mathbf{e}_n\) and let \(v_1,v_2,\cdots,v_n\) be the coordinates of a vector \(\mathbf{v}\). Then we define the norm as $$\|\mathbf{v}\|_0=\max_{1\leq i\leq n}|v_i|.$$ This should be easily verified to fit the three properties above. We also note by property two of norms that if the result holds for a vector \(\mathbf{v}\) then it will hold for the vector \(a\mathbf{v}\). We then only consider the vectors in the set \(S_n=\{v\in V\mid\|v\|_0=1\}\). Here we use the subscript to denote that this is a set in an \(n\) dimensional vector space.
We first show that this set is compact under the topology given. We see that the set \(C_n=\{v\in V\mid \|v\|_0\leq 1\}=[-1,1]^n\supset S_n\) must be compact, as it is the product of finitely many compact sets. Now since it is clear that \(S_n\) must be closed it follows that it is compact.
Now let \(\|\cdot\|_1\) be any norm on \(V\). We will show that it is a continuous function on the topology induced by \(\|\cdot\|_0\).
Fix \(\varepsilon\gt 0\) and consider any \(x,y\in V\) such that $$\|x-y\|_0\lt \frac{\varepsilon}{n\max\limits_{1\leq i\leq n}\|\mathbf{e}_i\|_1}.$$ We have that $$\|x\|_1-\|y\|_1=\|(x-y)+y\|_1-\|y\|_1\leq \|x-y\|_1$$ and so \(|\|x\|_1-\|y\|_1|\leq \|x-y\|_1\). Now, f \(x_i\) and \(y_i\) are the \(i\)th components of \(x\) and \(y\) respectively then \begin{align}|\|x\|_1-\|y\|_1|\leq& \left\|\sum (x_i-y_i)\mathbf{e}_i\right\|_1\\ \leq &\sum \|(x_i-y_i)\mathbf{e}_i\|_1\\ \leq &n\left(\max_i|x_i-y_i|\right)\left(\max_i\|\mathbf{e}_i\|_1\right)\\ \leq &n\|x-y\|_0\max_i\|\mathbf{e}_i\|_1\\ \lt &\varepsilon.\end{align} From the extreme value theorem, this norm restricted to \(S_n\) will take on a minimum and maximum values \(C_1\) and \(C_2\) respectively. That is, for all \(v\in V\) we have that $$C_1\leq \|v\|_1\leq C_2.$$ Now we also know that $\|v\|_0=1$ and so $$C_1\|v\|_0\leq \|v\|\leq C_2\|v\|_0.$$ This completes our proof. ∎

We should note here that this result only holds for finite dimensional vector spaces. Consider for example the vector space \(\mathcal{C}[1,\infty)\) and the norms given by \begin{align}\|f\|_1&=\int_1^\infty |f|\\ \|f\|_2&=\left(\int_1^\infty f^2\right)^{1/2}.\end{align} We see that \(\|1/x\|_2=1\), while \(\|1/x\|_1=\infty\). We have one result left to show, which deals with operator norms.
If \(A\colon V\to V\) is a linear operator on a finite dimensional space, then the operator norm is given by $$\|A\|=\sup_{x\neq \mathbf{0}} \frac{|A(x)|}{|x|}$$ where \(|x|\) refers to a given norm of a vector \(x\in V\). For our purpose, we will use \(|x|=\|x\|_0\) as defined above.

Note that we may also write $$\|A\|=\sup_{x\in S_n} |A(x)|$$ where \(S_n\) is defined above.
We now turn to the following theorem which will help relate the norms of operators with those of their representative matrices.
Theorem: Let \(L\colon V\to V\) be a linear operator on the \(n\)-dimensional vector space \(V\), and let \(M\in \mathbb{R}^{n^2}\) be its matrix representation. Then there are constants \(C_1,C_2\) such that \(C_1\|M\|_0\leq \|L\|\leq C_2\|M\|_0\).
Proof: The \(i\)th column of \(M\) is given by \(L(\mathbf{e}_i)\). It follows then that $$\|A\|_0=\max_i \|L(\mathbf{e}_i)\|_0.$$ This shows that \(\|A\|_0\leq \|L\|\). Now if we take some \(x\) with \(\|x\|=1\) we see that \begin{align}\|L(x)\|_0=&\left\|\sum x_i L(\mathbf{e_i})\right\|_0\\ \leq &\|x\|_0\sum \|L(\mathbf{e_i})\|\\ \leq &\|x\|_0\max_{1\leq i\leq n}\left\{\sum_{j=1}^n |a_{ij}|\right\}\\ \leq &n\|M\|_0\|x\|_0\end{align} which implies that \(\|L\|\leq n\|M\|_0\). The proof is complete. ∎

No comments:

Post a Comment