{'fraction_non_alphanumeric': 0.067769025454072, 'fraction_numerical': 0.010676388255972918, 'mean_word_length': 3.606296851574213, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On low rank perturbation of matrices

The article is devoted to different aspects of the question"What can be done with a matrix by low rank perturbation?"It is proved that one can change a geometrically simple spectrum drastically by a rank 1 permutation, but the situation is quite different if one restricts oneself to normal matrices. Also, the Jordan normal form of a perturbed matrix is considered. It is proved that with respect to rank as a distance all almost unitary matrices are near unitary.


Introduction
The article is devoted to different aspects of the question: "What can be done with a complex-valued matrix by a low rank perturbation?" 1 From the works of Thompson [15] we know how the Jordan normal form can be changed by a rank k perturbation, see Theorem 2. Particulary, it follows that one can do everything with a geometrically simple spectrum by a rank 1 perturbation, see Corollary 1. But the situation is quite different if one restricts oneself to normal matrices, see Theorem 3 and Corollary 2. We think that Corollary 2 may be considered as a finite dimension analogue of the continuous spectrum conservation under compact perturbations in Hilbert spaces. For unitary and self-adjoint matrices the inequality of Corollary 2 is the only restrictions on "what can be done with a spectrum by a rank k perturbation", see Theorem 4. We don't know if there is an analogue of Theorem 4 for normal matrices. It is worth to mention that Corollary 2 for self-adjoint matrices follows from Cauchy interlacing theorem [2]. Theorem 4 is related with the converse Cauchy interlacing theorem [6].
The spectrum of H 1 + H 2 with known spectra of self-adjoint matrices H 1 and H 2 is studied a lot, see [9] and the bibliography therein. Although the complete set of restrictions on the spectrum H 1 + H 2 known in this situation, we are not sure that there is an easy proof of Theorem 4 using results of [9].
Although Theorem 2 should be known (see, for example, [13], where Theorem 2 formulated in one direction), we will give a proof here, manly because our proof falls in a general framework , which is also used in the proof of Theorem 4. Let us describe the framework. The set C n×n of all complex n×nmatrices (set of self-adjoint matrices) we equip with the arithmetic distance, d(A, B) = rank(A − B) (see [3]). The arithmetic distance is geodesic for these cases. The spectral properties of matrices, such as Weyr characteristics and spectra (multiset) also may be considered as a metric spaces with distance, related to the arithmetic distance on matrices, see Section 2. These distances also turn out to be geodesic. Then we prove Theorem 2 (Theorem 4) for rank(A − B) = 1 and the general results will follow from Proposition 1. Proposition 1. Let X and Y be geodesic metric spaces, let O X n (x) denote the closed ball of radius n around x in X, let φ : X → Y be such that φ(O X 1 (x)) = O Y 1 (φ(x)) for all x ∈ X. Then φ(O X n (x)) = O Y n (φ(x)) for any n ∈ N and x ∈ X. Proof. The proof is by induction. For n = 1 there is nothing to prove.
Step n → n + 1: It follows In Section 5 and Section 6 we use the normalized arithmetic distance d r (A, B) = rank(A−B) n , where n is the size of the matrices. We are interested in the following questions: " Suppose that matrices almost satisfy some equations (in the sense of d r (·, ·)). If close to that matrices there exist matrices satisfying the equations (uniformly with respect to n)?" We manage to answer only the following: close to an almost unitary (self-adjoint) matrix there exists an unitary (self-adjoint) matrix. We do not know if the same is true for normal matrices. (This question has the affirmative answer for norm distance dn(A, B) = A − B , see [10]. It is equivalent to the following: "close to any pair of almost commuting self-adjoint matrices there exists a pair of commuting self-adjoint matrices (with respect to the distance dn(·, ·)). It is interesting that there are almost commuting (with respect to dn(·, ·)) matrices, close to which there are no commuting matrices, [4,5,16]). The similar question have been studied for operators in Hilbert spaces (Calkin algebras, [7]). In Hilbert spaces the operator a is called to be essentially normal iff aa * − a * a is a compact operator. In contrast with Theorem 7, there exists an essentially unitary operator which is not a compact perturbation of an unitary operator (just infinite 0-Jordan cell). There is a complete characterization of compact perturbations of normal operators, see [7] and the bibliography therein. Let us return to almost commuting matrices with respect normalized arithmetic distance d r . In Section 6 we show that for any A ∈ C n×n with simple spectrum there exists an almost commuting matrix, which is far from each commuting with A matrix. The similar problem for the pairs of almost commuting matrices, as far as we know, is open. Precisely, if for any ǫ > 0 there exists δ > 0 such that for any A, B, d r (AB, BA) < ǫ there exists (Ã,B) satisfying AB =BÃ and d r (Ã, A), d r (B, B) < δ (δ does not depends on size of the matrices).
We think that low rank perturbations of matrices may related to sofic groups. The following question seems to be interesting from this point of view (although it seems to goes beyond the scope of the present article). One can show that all solutions of equation On the other hand, it is true that for any ǫ > 0 there exist A, C, d(A, E) = d(C, E) = 1 and d(C −1 A −1 CAC −1 AC, A 2 ) < ǫ. If the above assertion is true with additional requirements C 4 = 1? If not, it gives an example of non-sofic group.
Note. All linear spaces are supposed to be finite dimensional in the rest of the article. C n×n will denote the set of all complex n × n-matrices, N = {0, 1, 2, ...}.
2 Some discrete geodesic spaces. • Set of all self-adjoint n × n matrices.
• Set of all unitary n × n matrices.
Remark 1. The methods used in the above proof are not applied for normal matrices -the set of normal matrices is not closed with respect neither summation nor multiplication. In fact, an example from [6] hints that arithmetic distance might be non geodesic on the set of normal matrices.

Proof. A Möbius transformation is a composition of linear transformations
2.2 Distance on the spaces of the Weyr characteristics.
Having in mind the Weyr characteristics of complex matrices (see below), we introduce the spaces ℑ n of the Weyr characteristics. Where ℑ n is the space of functions Z + × C → N, (i, λ) → η i (λ) such that • η i (λ) = 0 for finitely many (i, λ) only, and λ∈C i∈N η i (λ) = n.
First of all let us note that d(·, ·) is indeed a metric. Trivially, d(η, µ) = 0 implies η = µ and d(·, ·) satisfies triangle inequality as supremum (maximum) of semimetrics. It is clear, that d(µ, ν) is also well defined for µ and ν in different spaces of Weyr characteristics (for different n). We will need the following Proposition 3. Let µ ∈ ℑ m and n > m. Then there exists ν ∈ ℑ n such that for any η ∈ ℑ n , the inequality d(µ, η) ≥ d(ν, η) holds.

Distances dc anddc on finite multisets of the complex numbers.
Multisets and operations. The language of multisets is very convenient to deal with spectrums. We will need only finite multisets. For a multiset A let set(A) denote the set of elements of A, forgetting multiplicity. It is clear that a muiltiset maybe considered as the multiplicity function χ A : set(A) → N, for any x ∈ A we will suppose χ A (x) = 0. (For all cases, considered here, set(A) ⊂ C, so we can consider χ A : C → N = {0, 1, 2...}.) As far as the authors aware, there are several generalizations of the set-theoretical operations to multisets. We will need the following operations: • Intersection A ∩ X of a set X and a multiset A, Let as extend S toS which include interior of complements of circles and semiplains: Proposition 5.
• dc anddc are metrics on the finite multisubsets of C. Proof.
• The same as for the spaces of Weyr characteristics.
). Now the item follows by definition of dc (dc).
• First of all, due to A and B are finite multisets, for any semiplain p we can find a circle c such that

Proof. A Möbius transformation defines a bijection ofS.
We don't know if the metric dc is geodesic on the multisets with fixed cardinality, but its restriction on any circle o line is: Proof. By Proposition 6, it is enough to proof it for the unit circle. Let us start with the case when set(A) ∩ set(B) = ∅. Let Γ = set(A) ∪ set(B) ⊂ C 1 . Let |Γ| = r. We will cyclically anticlockwise order Γ = {γ 0 , γ 1 , ..., γ r−1 } by elements of Z r . To construct C we move each element of A to the next element in Γ, precisely, set(C) ⊆ Γ and for the other cases We will check that C satisfies our needs. For x, y ∈ Γ let [x, y] denote the closed segment of C 1 , starting from x and going anticlockwise to [γi,γj ] (C \ B, B \ C) ≤ −k.
In the first case we may assume that γ i , γ j ∈ C \ B and γ i−1 , γ j+1 ∈ C \ B. Now, changing interval if necessary (i n = i − 1 and (or) j n = j − 1) we may, keeping [γi,γj ] (C \ B, B \ C), achieve that γ i , γ j ∈ A and γ i−1 , γ j+1 ∈ A. Then We are going to reformulate Theorem 1 for the field C using Weyr characteristic. Let η m (A, λ) denote the number of λ-Jordan blocks in A of size greater or equal to m (m ∈ N).
Theorem 2. Let A ∈ C n×n with Weyr invariants η m (A, λ). Then as R ranges over all n × n complex matrices of rank less o equal k, the Weyr invariants assumed by the matrix B = A + R are precisely those, that satisfy both of the following conditions: Proof. It is enough to prove the theorem for k = 1. Indeed, assume that the theorem is valid for k = 1. Then we may consider the Weyr characteristics as a map ψ : C n×n → ℑ n , which satisfies Proposition 1. So, Theorem 2 follows, though it states that ψ(O k (A)) = O k (ψ(A)). Let us prove Theorem 2 for k = 1. For a given eigenvalue λ ∈ sp(A) the sequence of numbers corresponding to the sizes of the λ-Jordan blocks in the Jordan normal form of A are know as the Segre characteristics of A relative to λ, [14].
As Weyr characteristic is the conjugate partition of Segre characteristic, we can use Ferrers diagram to compute η m (B, λ) (see, [14]) as the number of points of column m in Ferrer diagram of the Segre characteristic of B relatively to λ (by short the Ferrer diagram of (B, λ)). Precisely, the Ferrer diagram for q(B, λ) is the set Figure 1 (the numbering from top to bottom and left to right). The Weyr characteristics is related with Ferrers diagram by the formula (Figure 1), which is equivalent to the fact that η j (B, λ) ≥ η j (A, λ) − 1. In similar form, from inequalities (1) we can observe that q i (A, λ) ≥ q i+1 (B, λ) with 1 ≤ i ≤ n − 1. Therefore, η j (A, λ) ≥ η j (B, λ) − 1, and the theorem follows.

Case of normal matrices.
We will say that the vector x is an α-eigenvector if Ax = αx. We will denote by R(A, λ, ǫ) the space generated by all the α-eigenvectors of A with |λ − α| ≤ ǫ. For the case of normal matrices, the following theorem shows that the difference between the dimension of R(A, λ, ǫ) and the dimension R(B, λ, ǫ) is bounded by the rank of the difference matrix A − B.
Theorem 3. If A and B are normal matrices, then for any λ, and for any ǫ ≥ 0, Let X ⊥ be the orthogonal complement of subspace X and P X be an orthogonal projection on X. Lemma 2. Let N : L → L be a normal operator, and X be a subspace of L such that (N −λ)x ≤ ǫ x for any x ∈ X, then (we will write R(λ, ǫ) for R(N, λ, ǫ)) Proof. It is clear that (1) (2) Similarly, Now we a ready to prove Theorem 3. Let rank(A − B) = r then there exists X = R(A, λ, ǫ) ∩ ker(A − B) with dim(X) ≥ dim(R(A, λ, ǫ)) − r and A| X = B| X , so (B − λ)| X ≤ ǫ and, by Lemma 2, dim(R(B, λ, ǫ)) ≥ dim(R(A, λ, ǫ)) − r. By symmetry, we get Theorem 3.
Theorem 3 implies that any circle in complex plain, containing m spectral points of A (B) should contain at least m − k spectral points of B (A). So, we have

Proof. It is just a reformulation of Theorem 3.
If the condition of Corollary 2 describes all accessible by rank k perturbation spectra? We are going to show that the answer is "yes" for self-adjoint and unitary matrices. In fact the following, more general result is valid: • It is enough to prove Theorem 5 for dc(sp(A), B) = 1 and the rest will follow from Proposition 1, Proposition 7 and Lemma 1.

So, we need to prove only
has a solution in (X, R) for unitary X and R of rank 1. Before solving Eq.2 let us introduce some notations and prove a proposition. For a finite A ⊂ R let P A (λ) = α∈A (λ−α). Let A and B be finite subsets of R of equal cardinality. It follows from interpolation that there exist unique x : A → A, such that (we write x α not x(α)). Moreover, x α = P B (α)/P A\{α} (α). Studying signs of P B (α) and P A\{α} (α) we trivially get Proposition 8. If A and B interlacing, then all x α in Eq.3 have the same sign.
Remark 2. In fact inverse of this proposition is also valid, see Lemma 1.20 of [8].
Now let us go back to solutions of Eq.2. For R = {r ij } fixed the equation has the unique solution X = {x ij }, with x ij = rij αi−βj . Now, suppose that rank(R) = 1 or, the same r ij = y i z j for some y, z ∈ C n , y, z = 0. When the matrix X is unitary? When its columns (rows) are orthonormal, or It follows that z j = 0 for all j = 1, ..., n, changing rows by columns we get the same for y. So, the difficult part is to guarantee that l.h.s. of Eq. 4 is 0 for j = k. Putting equality into Eq.4 and multiplying it by P A (β k )P A (β j )(β j − β k )/(z j z * k ) we get (after some elementary transformations): which imply that there exists c, such that for all j. Or the same, B is the set of roots of polynomial so |y i | 2 = P B (α i )/cP A\{αi} (α i ). Choosing c = 1 or c = −1, we get, by Proposition 8, that |y i | 2 is well defined. Now, take, for example, y i = |y i |. From Eq.4 for j = k we can find |z j | 2 . Then, taking z j = |z j | we get needed solution of Eq.2.

Almost unitary operators are near unitary operators with respect to normalized arithmetic distance
For A, B ∈ C n×n , let d r (A, B) be the normalized arithmetic distance: The following theorems says that "near" to any α-self-adjoint matrix there exists a self-adjoint matrix S, and that "near" to any α-unitary matrix there exists an unitary matrix U (for small α). The good illustrations for this theorem are 0-Jordan cells:    Proof. Let rank(A * A − E) = r, so there exist subspace X ⊂ L, dim(X) = n − r such that A * A| X = E| X . Consider A| X : X → Y = A(X). Under assumptions of the theorem A * (Y ) = X, it follows that (A| X ) * = A * | Y : Y → X, so A| X : X → Y is an unitary operator. Choose any unitary operator It is not clear if this proof could be adapted for normal matrices -unitary operator from an unitary space to another unitary space is well defined, but how to define normal operators between different unitary spaces...?
Question: If we define α-normal matrices in similar form to self-adjoint and unitary matrices, the equivalent of theorems 6 and 7 are true for normal matrices?
6 Almost commuting matrices Theorem 8. For every 4 ≤ n ∈ N and every A ∈ C n×n with simple spectrum there exists X ∈ C n×n such that d r (AX, XA) < 2/n and for any matrix B, commuting with A, d r (B, X) ≥ 1 2 . Before starting the proof of the theorem we need some facts.
Now we are ready to prove Theorem 8.