This study is motivated by a need to effectively determine the difference between a system fault and normal system operation under parametric uncertainty using eigenstructure analysis. This involves computational robustness of eigenvectors in linear state space systems dependent upon uncertain parameters. The work involves the development of practical algorithms which provide for computable robustness measures on the achievable set of eigenvectors associated with certain state space matrix constructions. To make connections to a class of systems for which eigenvalue and characteristic root robustness are well understood, the work begins by focusing on companion form matrices associated with a polynomial whose coefficients lie in specified intervals. The work uses an extension of the well known theories of Kharitonov that provides computational efficient tests for containment of the roots of the polynomial (and eigenvalues of the companion matrices) in “desirable” regions, such as the left half of the complex plane.