Your claim is true. It suffices to modify the proof in your question slightly. If the algebraic and geometric multiplicities of some eigenvalue $\lambda$ coincide, then $A=P\pmatrix{\lambda I\\ &M}P^{-1}$ for some change-of-basis matrix $P$ and some submatrix $M$ that is the direct sum of the Jordan blocks for other eigenvalues. Therefore $u^T=e_1^TP^{-1}$ and $v=Pe_1$ are respectively a left eigenvector and a right eigenvector corresponding to $\lambda$, with $u^Tv=1\ne0$.
$A$ and $A^T$ have identical eigenvalues basically because a matrix $B$ (take $B=\lambda I-A$ in your case) is singular if and only if its $B^T$ is singular. And the geometric reason for the latter to hold is that every linear map on a finite-dimensional vector space can be decomposed into the product of a number of shears, transpositions and also a scaling function. That is, $B=E_1E_2\ldots E_kDF_\ell\ldots F_2F_1$ where each $E_i$ or $F_j$ is either a shear matrix (an elementary row/column operation for row/column addition) or a transposition matrix (an elementary operation for exchanging two rows/columns) and $D$ is a scaling (diagonal) matrix. As shear matrices are nonsingular, $B$ is singular iff $D$ is singular iff $B^T$ is singular.
Let $D$ be the diagram of a link. For example, $D$ could be the diagram of the Celtic knot or link pictured in your post. Let $G$ be the checkerboard graph of $D$. The graph $G$ is the graph described in your first bullet point.
Answer: The number of components of $D$ is determined by the abstract graph $G$ and does not depend on how $G$ is embedded in the plane.
To the best of my knowledge, this was first proved by Michel Las Vergnas in 1979. He showed that the number of components of $D$ is determined by the Tutte polynomial evaluation $T_G(-1,-1)$. Since the Tutte polynomial doesn't depend on a particular embedding of $G$, the result follows. The reference for this paper is
- Las Vergnas, Michel. On Eulerian partitions of graphs. Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), pp. 62–75,
Res. Notes in Math., 34, Pitman, Boston, Mass.-London, 1979.
I could not easily find a copy of the above paper, so here's another way to get the solution, due to Dan Silver and Susan Williams (arXiv link). They define a matrix $Q_2(G)$ whose entries are in the field with two elements $\mathbb{F}_2$ as follows. Both the rows and columns of the matrix are indexed by the vertices $v_1,\dots,v_n$ of $G$. If $i\neq j$, then the $ij$ entry of $Q_2(G)$ is the number of edges between vertices $v_i$ and $v_j$ (taken$\mod 2$). The $ii$ entry of $Q_2(G)$ is the sum of the other entries in the row $i$ (again taken$\mod 2$). Equivalently, we could say the $ii$ entry in $Q_2(G)$ is the sum of the other entries in the column $i$.
In Theorem 1.1 of the linked paper, they prove that the number of components of $D$ equals the nullity of $Q_2(G)$. They note in Remark 1.2 that this implies the number of components of $D$ is independent of the plane embedding of $G$.
Edit: I don't have access to the Las Vergnas paper, but I can give another explanation of the result using the Tutte polynomial and the Jones polynomial.
Let $L$ be an alternating link, let $D$ be an alternating diagram of the link, and let $G$ be the checkerboard graph of $D$. Then the Tutte polynomial $T_G(x,y)$ of $G$ and the Jones polynomial $V_L(t)$ of $L$ are related as follows:
$$V_L(t) = f_D(t) T_G(-t,-t^{-1})$$
for the function $f_D(T)$ defined by
$$f_D(t) = (-1)^{w(D)}t^{\frac{1}{4}(|E| - 2(|V|-1)+3w(D))}$$
where $w(D)$ is the writhe of $D$, $|E|$ is the number of edges in $G$, and $|V|$ is the number of vertices of $D$. Notice that $|f_D(1)|=1$, and thus $|V_L(1)| = |T_G(-1,-1)|$.
The Jones polynomial satisfies the skein relation
$$(t^{\frac{1}{2}}-t^{-\frac{1}{2}})V_{L_0}(t) = t^{-1}V_{L_+}(t) - tV_{L_-}(t)$$
where $L_+,L_-,$ and $L_0$ are as below.
Setting $t=1$ in the above skein relation yields $V_{L_+}(1)=V_{L_-}(1)$. In other words the Jones polynomial evaluated at $t=1$ does not change under crossing changes, and thus $V_L(1)=V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)$ where $\bigcirc\sqcup\dots\sqcup\bigcirc$ is the trivial link with the same number of components as $L$. The Jones polynomial of $\bigcirc\sqcup\dots\sqcup\bigcirc$ is $V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(t) = (-t^{\frac{1}{2}}-t^{-\frac{1}{2}})^{m-1}$ where $m$ is the number of components of $\bigcirc\sqcup\dots\sqcup\bigcirc$. Thus
$$|T_G(-1,-1)|=|V_L(1)|=|V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)| = 2^{m-1}.$$
The above case handles when $L$ is alternating. If $L$ is non-alternating, then proceed as follows. Let $D$ be any diagram of $L$. Define $D_{\text{alt}}$ to be a diagram with the same shadow as $D$ but whose crossings are changed to be alternating, and define $L_{\text{alt}}$ to be the link whose diagram is $D_{\text{alt}}$. Note that $D$ and $D_{\text{alt}}$ have the same checkerboard graph $G$. The above argument implies that $|T_G(-1,-1)|=2^{m-1}$ where $m$ is the number of components of $L_{\text{alt}}$. Since $L_{\text{alt}}$ and $L$ have the same number of components, the result follows for $L$ as well.
Best Answer
There seems to be a typo in your question. If you mean $w^TA=\lambda w^T$, then $w$ is a left eigenvector rather than a right eigenvector of $A$.
At any rate, your observation has little to do with adjacency matrices of strongly connected graphs. Suppose $A$ is any real square matrix with a real unit right eigenvector $v$ and a real unit left eigenvector $w$ for the same eigenvalue $\lambda\in\mathbb R$, so that $Av=\lambda v$ and $w^T A=\lambda w^T$. Then $$ \|w^T A\|=|\lambda|=|v^T(Av)|=|(v^T A)v|\le\|v^T A\|\|v\|=\|v^T A\|.\tag{1} $$ Similarly, $$ \|Av\|=|\lambda|=|(w^T A)w|=|w^T(Aw)|\le\|w\|\|Aw\|=\|Aw\|.\tag{2} $$ By Cauchy-Schwarz inequality, equality holds in $(1)$ if and only if $v^T A$ is a scalar multiple of $v^T$, i.e. if and only if $v$ is also a left eigenvector of $A$. Similarly, equality holds in $(2)$ if and only if $w$ is also a right eigenvector of $A$. This occurs when $A$ is symmetric, but this may also happen otherwise. E.g. $$ A=\pmatrix{0&1&0\\ 0&0&1\\ 1&0&0} $$ isn't symmetric, but $v=w=\frac{1}{\sqrt{3}}(1,1,1)^T$ is both a left and a right Perron vector of $A$ and $\|v^TA\|=\|w^TA\|=\|Av\|=\|Aw\|=1$.