Do commuting matrices share the same eigenvectors?

The answer is in the book Linear Algebra and its Application by Gilbert Strang. I'll just write down what he said in the book.

Starting from $Ax=\lambda x$, we have

$$ABx = BAx = B \lambda x = \lambda Bx$$

Thus $x$ and $Bx$ are both eigenvectors of $A$, sharing the same $\lambda$ (or else $Bx = 0$). If we assume for convenience that the eigenvalues of $A$ are distinct – the eigenspaces are one dimensional – then $Bx$ must be a multiple of $x$. In other words $x$ is an eigenvector of $B$ as well as $A$.

There's another proof using diagonalization in the book.

Commuting matrices do not necessarily share all eigenvector, but generally do share a common eigenvector.

Let $A,B\in\mathbb{C}^{n\times n}$ such that $AB=BA$. There is always a nonzero subspace of $\mathbb{C}^n$ which is both $A$-invariant and $B$-invariant (namely $\mathbb{C}^n$ itself). Among all these subspaces, there exists hence an invariant subspace $\mathcal{S}$ of the minimal (nonzero) dimension.

We show that $\mathcal{S}$ is spanned by some common eigenvectors of $A$ and $B$. Assume that, say, for $A$, there is a nonzero $y\in \mathcal{S}$ such that $y$ is not an eigenvector of $A$. Since $\mathcal{S}$ is $A$-invariant, it contains some eigenvector $x$ of $A$; say, $Ax=\lambda x$ for some $\lambda\in\mathbb{C}$. Let $\mathcal{S}_{A,\lambda}:=\{z\in \mathcal{S}:Az=\lambda z\}$. By the assumption, $\mathcal{S}_{A,\lambda}$ is a proper (but nonzero) subspace of $\mathcal{S}$ (since $y\not\in\mathcal{S}_{A,\lambda}$).

We know that for any $z\in \mathcal{S}_{A,\lambda}$, $Bz\in \mathcal{S}$ since $\mathcal{S}_{A,\lambda}\subset\mathcal{S}$ and $\mathcal{S}$ is $B$-invariant. However, $A$ and $B$ commute so $$ ABz=BAz=\lambda Bz \quad \Rightarrow\quad Bz\in \mathcal{S}_{A,\lambda}. $$ This means that $\mathcal{S}_{A,\lambda}$ is $B$-invariant. Since $\mathcal{S}_{A,\lambda}$ is both $A$- and $B$-invariant and is a proper (nonzero) subspace of $\mathcal{S}$, we have a contradiction. Hence every nonzero vector in $\mathcal{S}$ is an eigenvector of both $A$ and $B$.

EDIT: A nonzero $A$-invariant subspace $\mathcal{S}$ of $\mathbb{C}^n$ contains an eigenvector of $A$.

Let $S=[s_1,\ldots,s_k]\in\mathbb{C}^{n\times k}$ be such that $s_1,\ldots,s_k$ form a basis of $\mathcal{S}$. Since $A\mathcal{S}\subset\mathcal{S}$, we have $AS=SG$ for some $G\in\mathbb{C}^{k\times k}$. Since $k\geq 1$, $G$ has at least one eigenpair $(\lambda,x)$. From $Gx=\lambda x$, we get $A(Sx)=SGx=\lambda(Sx)$ ($Sx\neq 0$ because $x\neq 0$ and $S$ has full column rank). The vector $Sx\in\mathcal{S}$ is an eigenvector of $A$ and, consequently, $\mathcal{S}$ contains at least one eigenvector of $A$.

EDIT: There is a nonzero $A$- and $B$-invariant subspace of $\mathbb{C}^n$ of the least dimension.

Let $\mathcal{I}$ be the set of all nonzero $A$- and $B$-invariant subspaces of $\mathbb{C}^n$. The set is nonempty since $\mathbb{C}^n$ is its own (nonzero) subspace which is both $A$- and $B$-invariant ($A\mathbb{C}^n\subset\mathbb{C}^n$ and $B\mathbb{C}^n\subset\mathbb{C}^n$). Hence the set $\mathcal{D}:=\{\dim \mathcal{S}:\mathcal{S}\in\mathcal I\}$ is a nonempty subset of $\{1,\ldots,n\}$. By the well-ordering principle, $\mathcal{D}$ has the least element and hence there is a nonzero $\mathcal{S}\in\mathcal{I}$ of the least dimension.

(Modified) Answer of Qiaochu Yuan here: This is false in a sort of trivial way. The identity matrix $I$ commutes with every matrix and has eigenvector set all of the underlying vector space $V$, but no other matrix except a multiple of the identity matrix has this property.

As noted in another answer, the statement is not true as stated, just take $$ A = \begin{bmatrix}1&0\\0&1\\\end{bmatrix}, \qquad B = \begin{bmatrix}1&0\\0&2\\\end{bmatrix}. $$

What is true is that, if $A$ and $B$ are diagonalizable, then $A$ and $B$ can be simultaneously diagonalized. Thanks to Thomas Andrews for pointing out an oversight.

Applying $B$ to both sides of $\lambda \xi = A \xi$ you get $\lambda (B \xi) = B A \xi = A (B \xi)$, so either $B \xi = 0$, or $B \xi$ is an eigenvector for $A$ with respect to the eigenvalue $\lambda$.

In any case $B$ maps the eigenspace $W$ of $A$ relative to the eigenvalue $\lambda$ into itself. On $W$, $A$ acts like the scalar $\lambda$. Now one can put $B$ in diagonal form on $W$ without changing the scalar shape of $A$ on $W$.

Matrices $A = \pmatrix{0&1\\0&0}, B = \pmatrix{1&0\\0&1}$ commute, but they don't share the eigenvector $\pmatrix{0\\1}$ of $B.$