Skip to main content
MathOverflow

Return to Answer

added 39 characters in body
Source Link
user66216
user66216
  • 46
  • 2
  1. 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).

  1. 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^T Z$ and $Z Z^T$$Z + iI$ to find one of the left- and right-singular vectorsleading eigenvectors of $Z$. the other extreme eigenvector is its conjugate.

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

Help is above.

  1. 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).

  1. 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^T Z$ and $Z Z^T$ to find the left- and right-singular vectors.

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

Help is above.

  1. 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).

  1. 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.

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

Help is above.

Source Link
user66216
user66216
  • 46
  • 2

  1. 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).

  1. 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^T Z$ and $Z Z^T$ to find the left- and right-singular vectors.

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

Help is above.