On spectrum of an adjacencies matrix of almost-complete graph

Let A𝑀𝑁 be a × matrix composed of 𝑁2 -𝑀 unities and zeroes. Considered as an adjacencies matrix, A𝑀𝑁 corresponds to a complete digraph with loops on vertices with some out of 𝑁2 edges removed. Someimportant properties of a graph are determined by its spectrum. For example Wang et al. [4] proposed a discrete-time model of viral propagation in a network. In that model a virus will die out or linger on depending on whether the ratio of curing and infection rates is below or above the treshold value. As Wang et al. have shown that treshold value is the spectral radius of the adjacencies matrix of the network graph, i.e. the maximal absolute value of its eigenvalues. More comprehensive description of spectral graph theory and its application is given by Cv`etkovic et al. [3]. This article analyzes spectral properties of such matrices. The matrix A𝑀𝑁 can be represented in the form A𝑀𝑁 = -B𝑀𝑁, where is a ×𝑁 matrix whose all entries are ones and ℬ𝑀𝑁 has unities exactly at these places where A𝑀𝑁 has zeroes. The spectrum of can be easily computed: 2 = 𝑁𝒥, so ( - 𝑁) is the minimal annihilating polynomial of and hence the spectrum of is (𝒥𝑁) = {0,𝑁}. For small enough the eigenvalues of A𝑀𝑁 will be “close” to those of 𝒥𝑁. Then The Method of Similar Operators [1; 2] is used, which allows in the case of perturbation of some ideal object (whose properties are known) to find an element of the algebra under consideration similar to the disturbed one yet having “simpler” structure. Via this method the following theorem is proven: Theorem. Let