3
$\begingroup$

It is relatively easy to show for a real symmetric matrix $ A $ that its eigenvectors belonging to distinct eigenvalues are orthogonal; it comes down to $(\lambda_i - \lambda_j) u_i^Tu_j=0$ and since eigenvalues are different; the eigenvectors have to be orthogonal. When the eigenvalues are equal, I know that we can pick eigenvectors which are orthogonal to eachother and to all other eigenvectors, enabling to build an orthogonal basis of eigenvectors which span $\mathbb {R^N} $ for a $ N \times N $ matrix. I try to show how one can pick orthogonal vectors for a shared eigenvalue $\lambda $. I tried to use the characteristic polynomial $ det (A - \lambda I_N)=0$ which has multiple roots at a shared eigenvalue $\lambda $. Assuming that $\lambda $ has multiplicity of $ m $ I tried to show then the matrix $ A - \lambda I_N $ has an $ m $ dimensional nullspace, spanned by $ m $ eigenvectors, but failed to reach any conclusions. How can we construct a proof of that?

$\endgroup$
  • 1
    $\begingroup$ Gram-Schmidt on each eigenspace with dimension larger than one. $\endgroup$ – Will Jagy Nov 21 '15 at 17:04
  • $\begingroup$ How should we ensure that $ m $ multiplicity for an eigenvalue corresponds to $ m $ dimensional eigenspace, in other words how can I show that the eigenvectors of this eigenvalue are linearly independent? This is where I got stuck, actually. $\endgroup$ – Ufuk Can Bicici Nov 21 '15 at 17:38
  • $\begingroup$ Should be in your book, every real symmetric matrix has a basis of eigenvectors. That does not mean that the particular vectors you choose for one of the eigenvalues are independent. It does mean that, if you are careless and take some dependent vectors, there are others that can be found with care. One way to force independence is just to keep doing gram-Schmidt every time you add an eigenvector for that eigenvalue,. i think i will post my example, 10 by 10. $\endgroup$ – Will Jagy Nov 21 '15 at 17:43
4
$\begingroup$

The typical approach to this problem is not to show directly that an eigenvalue with multiplicity $m$ for a symmetric matrix has an $m$-dimensional space of corresponding eigenvectors but to use an inductive argument which shows it indirectly. In order to do that, it is more comfortable to talk about self-adjoint maps instead of real symmetric matrices (because the induction is done by letting the matrix act on an invariant subspace which doesn't correspond neatly to a submatrix or something like that).

Given a self-adjoint linear map $T \colon \mathbb{R}^n \rightarrow \mathbb{R}^n$ you can show three things:

  1. If $W \subseteq \mathbb{R}^n$ is $T$-invariant subspace ($T(W) \subseteq W$) then $W^{\perp}$ is also $T$-invariant. This is done by a straightforward calculation.
  2. If $W \subseteq \mathbb{R}^n$ is $T$-invariant then $T|_W \colon W \rightarrow W$ is also self-adjoint with respect to the inner-product on $W$ obtained by restricting the standard inner-product on $\mathbb{R}^n$.
  3. The map $T$ has a eigenvector - that is, there exists $0 \neq v \in \mathbb{R}^n$ such that $T(v) = \lambda v$ for some $\lambda \in \mathbb{R}$. This is quite delicate. If $T(v) = Av$ for a symmetric $A \in M_n(\mathbb{R})$ then one way to see it is to let $A$ act on $\mathbb{C}^n$ and consider $S \colon \mathbb{C}^n \rightarrow \mathbb{C}^n$ given by $S(v) = Av$. The map $S$ is still self-adjoint and so has real eigenvalues. Since we are working over the complex numbers, the map $S$ must have a complex eigenvector $w \in \mathbb{C}^n$ with $Sw = Aw = \lambda w$ for $\lambda \in \mathbb{R}$. But $\mathrm{rank}_{\mathbb{C}} |\lambda I - A| = \mathrm{rank}_{\mathbb{R}} |\lambda I - A|$ there must also be a non-zero real vector $v \in \mathbb{R}^n$ with $Av = \lambda v$.

Assuming you have shown the items above, you can show that $T$ must be diagonalizable by an inductive argument. Start with an eigenvector $0 \neq v \in \mathbb{R}^n$ for $T$ and let $W := \mathrm{span} \{ v \}$. Then $W$ is $T$-invariant and so $W^{\perp}$ is $T$-invariant and $T|_{W^{\perp}} \colon W^{\perp} \rightarrow W^{\perp}$ is self-adjoint. Repeat the argument for $T|_{W^{\perp}}$. In the end you'll obtain an orthogonal basis $(v_1, \ldots, v_n)$ of eigenvectors for $T$ which shows that $T$ is diagonalizable and indirectly shows that the algebraic multiplicity of each eigenvalue must coincide with the geometric multiplicity.

$\endgroup$
1
$\begingroup$

This seems to address your problem, I found a very nice basis for the eigenvectors of a matrix with all entries $1.$ The reason we know the columns are independent is that they are perpendicular to each other, ordinary dot product of columns is zero. I am encouraging you to do something along these lines.

$$ \left( \begin{array}{rrrrrrrrrr} 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 2 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 3 & -1 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 4 & -1 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 5 & -1 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 6 & -1 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 7 & -1 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 8 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 9 \end{array} \right). $$

The columns of $P$ are of varying lengths; for the 10 by 10 case depicted, lengths $ \sqrt{10}, \sqrt{2}, \sqrt{6}, \sqrt{12},..$ All that is necessary to make an orthogonal matrix $Q$ out of this is to divide each column by its length.

$\endgroup$
  • $\begingroup$ Thanks for the answer. I think I have incorrectly formulated my original question. What I really want to show is the following: We have real symmetric matrix $A$ and it has an eigenvalue $\lambda$ with multiplicty of $m$ (Algebraic, $m$ times the root of the characteristic polynomial). What I want to show is then, that the nullspace of $A-\lambda I$ has dimension of $m$, as well. Once I show that, I am aware that I can apply Gram-Schmidt on the basis vectors of the nullspace. $\endgroup$ – Ufuk Can Bicici Nov 21 '15 at 19:56
  • $\begingroup$ @BattleBeast That is roughly what I thought. As I said, with symmetric matrix, there is a basis of eigenvectors. Look up the proof, it will deal with your issue as part of the proof. What book are you using? $\endgroup$ – Will Jagy Nov 21 '15 at 19:59
  • $\begingroup$ Actually, I am not following a book exactly. I knew that a symmetric real matrix has orthogonal eigenvectors for distinct eigenvalues but I wondered hot repeated eigenvalues are handled. I use symmetric matrices for Principal Component Analysis mostly and in practice you never get repeated eigenvalues (well, almost). In the appendix of a Machine Learning book I read some time ago, it is said: "(it can be shown that the degenerate eigenvectors are never linearly dependent)". This is said for a real,symmetric matrix. I wondered how this is shown and I ended up here. $\endgroup$ – Ufuk Can Bicici Nov 21 '15 at 22:03
  • $\begingroup$ In your example, we have a rank 1 matrix, so, 9 eigenvalues are equal to 0, yet you built 9 orthogonal and linearly independent vectors for that eigenvalue, if I understood correctly. How do we proceed in the general case? @levap gave a good answer, but it has references into the functional analysis which is too advanced for me. I am looking for a proof which is less or more contained in the domain of linear algebra. $\endgroup$ – Ufuk Can Bicici Nov 21 '15 at 22:07
  • $\begingroup$ @BattleBeast, then I recommend the first book by Horn and Johnson, called Matrix Analysis (1985) which emphasizes matrices over more general linear algebra. I have no idea what your Machine Learning book might mean by "degenerate eigenvalues." $\endgroup$ – Will Jagy Nov 21 '15 at 22:07
0
$\begingroup$

All eigenvectors sharing a common eigenvalue $\lambda $ form a subspace: the kernel of the operator $A-\lambda I$. Using the Gram-Schmidt process we can construct an orthonormal basis for this subspace. The vectors of this basis have the needed properties.

$\endgroup$
  • $\begingroup$ What I am after is actually to find that: $\lambda $ has a multiplicty of $ m $. Then the nullspace of $ A-\lambda I $ has a dimension of $ m $. Is there a way to show that as well, I know that once we find $ m $ linearly independent basis vectors, we can apply Gram-Schmidt. $\endgroup$ – Ufuk Can Bicici Nov 21 '15 at 19:05
  • $\begingroup$ @battlebeast You can find a proof of the fact that the geometric and algebraic multiplicities are equal in Halmos' Finite Dimensional Vector Spaces, chapter 78, theorem 6. If I have time I'll add it to my answer. It uses some previously proven results from chapter 53 $\endgroup$ – dafinguzman Nov 22 '15 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.