We consider robust stability analysis of a class of large scale interconnected systems. The individual subsystems may be different but they are assumed to share a property that characterizes a set of interconnection matrices which lead to stable overall systems. The main contribution of the paper is to show that, for the case where the network interconnection matrix is normal, (robust) stability verification can be simplified to a low complexity problem of checking whether the frequency response of the individual subsystems and the eigenvalues of the interconnection matrix can be mutually separated using a class of quadratic forms. Most interestingly, it is shown that this criterion is also necessary, in the sense that if the criterion is violated, an interconnection matrix of the same eigenvalue distribution can be found to make the overall system unstable. (C) 2008 Elsevier Ltd. All rights reserved.