A Geometric Approach to Computing Bounds on Perturbations of Invariant Subspaces of Normal Matrices with Application to a Graph Connection Problem

We provide upper bounds on the perturbation of invariant subspace of normal matrices measured using a metric in the space of vector subspaces of $\mathbb{C}^n$. We derive the upper-bounds in terms of (1) the spectrum of both the unperturbed and perturbed matrices, as well as, (2) the spectrum of the unperturbed matrix only. We show that if the spectrum is well-clustered (a relation formally described as "separation-preserving perturbation"), the later kind of upper-bound is possible and the corresponding perturbed subspace is also computable. All results are computationally favorable (e.g., computing the bounds do not require combinatorial searches or solving non-trivial optimization problems). We apply the result to a graph perturbation problem.