Extremal eigenvalues & eigenvectors of skew-adjacency matrix I am looking for ways to obtain the extremal eigenvalues and eigenvectors of the skew-adjacency matrix of a directed graph without diagonalizing it. The graphs I am interested in are not regular (but they have a maximum degree) or bipartite. They may or may not be planar.


*

*Are there any bounds for either of the extremal eigenvalues of the skew-adjacency matrix?

*Are there any bounds to the entries of the eigenvectors corresponding to the extremal eigenvalues that I can obtain without diagonalizing the skew-adjacency matrix?

*Suppose that I know that the extremal eigenvalues of the skew-adjacency matrix are degenerate. Does this tell me anything useful related to the above questions?

 A: *

*Are there any bounds for either of the extremal eigenvalues of the skew-adjacency matrix?


Yes. In particular, the extremal eigenvalue bounds the "asymmetry of arcs" between large subsets of vertices. See for example, "Discrepancy Inequalities for Directed Graphs", Discrete Applied Mathematics, 176 (2014), pp. 30-42.) (though the article focuses on Markov chains, similar results can be obtained for the adjacency case- though not as pretty).


*Is there a way to obtain the eigenvector corresponding to either of the extremal eigenvalues without diagonalizing the skew-adjacency matrix?


Yes. Consider $Z = A - A^T$. Then the eigenvectors corresponding to extreme eigenvalues of $Z$ are precisely $f \pm ig$ where $f$ and $g$ are the real left- and right- singular vectors of $Z$. This is a lemma in the paper above. Hence, you can apply the power method to $Z + iI$ to find one of the leading eigenvectors of $Z$. the other extreme eigenvector is its conjugate.


*Are there any known results that may help with either of the above?


Help is above.
A: Complexification. Let $A$ be a real $n\times n$ matrix such that $A^T=-A$. Let us define
$
B=iA, i=\sqrt{-1}.
$
We have
$$
B^*=\overline{B}^T=-iA^T=iA=B,
$$
so that $B$ is self-adjoint on $\mathbb C^n$: as a consequence
$$
B=\sum_{1\le j\le r}\lambda_j\mathbb P_j,\quad \lambda_j\in \mathbb R, \mathbb P_j \text{ orthogonal projection onto $E_{\lambda_j}$}, \oplus_{1\le j\le r}E_{\lambda_j}=\mathbb C^n,
$$
so that 
$A=\sum_{1\le j\le r}(-i\lambda_j)\mathbb P_j$.
This reduces the analysis of a skew-adjoint operator to the study of a selfadjoint operator.
