J Charles Gilbert

Equivalent R-linear and C-linear systems of equations

Keywords: C-linear system of equations, R-linear system of equations in complex numbers, equivalence of linear systems, row reduction of an R-injective matrix in complex numbers : 15A06, 15A99, 65F99

This paper addresses two elementary subjects in linear algebra, intertwining concepts in real and complex numbers, which could be proposed as homework assignments to students learning complex linear algebra. First, given an R-linear system of equations with data in complex numbers, necessary and sufficient conditions are given ensuring that there exists a C-linear system of equations of the same size that has the same solution set whatever is the constant term of the original system. The motivation for searching for such an equivalence may be theoretical or based on a numerical efficiency wish. This first result rests on the second contribution of the paper, which claims that, being given an R-injective matrix M ∈ C m×(2n) -such a matrix must have more rows than half the number of its columns -one can find a matrix H ∈ C n×m such that HM ∈ C n×(2n) is also R-injective.

The analysis of the semidefinite optimization (SDO) problem in complex numbers [START_REF] Gilbert | Plea for a semidefinite optimization solver in complex numbers[END_REF] has highlighted a topic in elementary linear algebra, intertwining concepts in real and complex numbers, that we consider to deserve clarification and a specific exposition. We generalize it a little here to make it useful in other contexts. This topic deals with the possibility to have an equivalence between an R-linear and a C-linear system of equations of the same size. By equivalence, we mean that the two systems have the same solution set, whatever is the right-hand side (or constant term) of the R-linear system. The proposed method to analyze this question makes use of the row reduction of an R-injective complex matrix, which is the second subject that is discussed with some details in this paper. We have not found these twentieth century themes in monographs such as [START_REF] Gantmacher | Théorie des Marices[END_REF][START_REF] Horn | Matrix Analysis[END_REF][START_REF] Horn | Topics in Matrix Analysis[END_REF][START_REF] Golub | Matrix Computations[END_REF][START_REF] Higham | Accuracy and Stability of Numerical Algorithms[END_REF], probably because of their easy access and very specific domain of application.

Let us be more precise. Consider the problem of solving the following R-linear system of equations, in complex numbers:

M x + N x = p, (1.1)
where M and N ∈ C n×n are given complex square matrices of order n, the right-hand side p ∈ C n is also given, and the unknown x ∈ C n appears together with its conjugate x in the system. Observe that the left-hand side of the system (1.1) is R-linear in x, but not necessarily C-linear (see the notation section below for a precise definition of these notions). It is easy to solve (1.1), or try to solve it, by transforming the system into real numbers. After equating the real and imaginary parts of (1.1), which justifies the 2n equations below, one gets (see also section 3.1)

ℜ(M ) + ℜ(N ) -ℑ(M ) + ℑ(N ) ℑ(M ) + ℑ(N ) ℜ(M ) -ℜ(N ) ℜ(x) ℑ(x) = ℜ(p) ℑ(p) , (1.2)
where ℜ and ℑ are used to designate the real and imaginary parts of an object in complex numbers (here, vectors or matrices). The size 2n of this system is twice as large as the one of (1.1). Despite its real nature, on paper, solving (1.2) by Gaussian elimination requires twice more real operations than solving an order n complex system (section 3.1). Therefore, the question arises to know whether (1.1) can be rewritten as a C-linear system in x ∈ C n of the form

Ax = Bp + Cp, (1.3)
where A, B, and C ∈ C n×n , in such a way that (1.1) and (1.3) have the same solution sets, whatever is p ∈ C n (we then say below that the two systems are equivalent ). The numerical interest of (1.3) over (1.1) now depends on the time needed to compute the new matrices A, B, and C, which is case dependent (this is discussed in section 3.1 and in the paragraph before proposition 3.4). The question of the equivalence between (1.1) and (1.3) may also have a purely theoretical interest. Actually, the transformation of (1.1) into an equivalent system of the form (1.3) is not always possible even if the number of equations of the systems is different. As an elementary example, suppose that n = 1, M = 1, N = i, and p = 0.

(1.4)

If, with this data, the R-linear system (1.1) was equivalent to a C-linear system of the form (1.3) (here for a fixed p), the solution x = 1i to (1.1) should satisfy A(1i) = 0 (since p = 0), implying that A should vanish; but then, the set of solutions to (1.3) would be C, while x = 1 is not a solution to (1.1); we get a contradiction with the claimed equivalence of the systems. One of the two goals of this paper is therefore to give necessary and sufficient conditions (NSC) on M and N ensuring the existence of matrices A, B, and C ∈ C n×n , such that the two systems (1.1) and (1.3) are equivalent (proposition 3.8). This theme is considered in section 3.

The proposed method to obtain the necessary and sufficient conditions quoted above is grounded on the row reduction of an R-injective matrix M ∈ C m×(2n) (it is a matrix such that any real vector α ∈ R 2n satisfying M α = 0 vanishes). For such a matrix, there holds m n (lemma 2.2) but it is not always possible to remove mn rows from M while preserving the R-injectivity of the resulting matrix (section 2.2). Nevertheless, it is shown in proposition 2.8 that there exists a matrix H ∈ C n×m , say a row reduction matrix, such that HM ∈ C n×(2n) is R-injective. The existence of the row reduction matrix H is proved algorithmically (sections 2.3 and 2.4), by a method that may require up to n iterations (section 2.5). The case of a matrix M with an odd number of columns is also addressed (proposition 2.9). This theme is considered in section 2.

Notation

The pure imaginary number is denoted by i := √ -1, while ℜ(ς) and ℑ(ς) are the real and imaginary parts of a complex object ς, which may be a number, a vector, or a matrix. The conjugate of such a object ς = ℜ(ς) + iℑ(ς) is defined and denoted by ς := ℜ(ς) -iℑ(ς).

We denote by C n R the R-linear vector space C n with the scalars restricted to R (instead of C). A map ℓ :

C n R → C m R is said to be R-linear if ℓ(αx + x ′ ) = αℓ(x) + ℓ(x ′
) for all x and x ′ ∈ C n and all α ∈ R. The map ℓ : C n → C m is said to be C-linear if the previous identity also holds for all α in C. The vector space of complex m × n matrices is denoted by C m×n (and by C m×n x ∈ C n }. We denote by I n the identity matrix of order n.

2 Row reduction of an R-injective complex matrix

Two bijections and one injection

It is convenient to introduce the R-linear bijection T ≡ T C n R : C n R → R 2n that transforms a complex vector in its real and imaginary parts, hence defined at x ∈ C n by

T(x) ≡ T C n R (x) = ℜ(x) ℑ(x) . (2.1)
A similar transformation can be introduced for matrices; it is the R-linear bijection

T ≡ T C m×n R : C m×n R → R (2m)×n , defined at M ∈ C m×n R by T(M ) ≡ T C m×n R (M ) := ℜ(M ) ℑ(M ) . (2.2)
Let us also introduce the R-linear operator

J ≡ J C m×n R : C m×n R → R (2m)×(2n) defined at M ∈ C m×n R by J(M ) ≡ J C m×n R (M ) = ℜ(M ) -ℑ(M ) ℑ(M ) ℜ(M ) .
This one is injective (but not surjective) and a ring homomorphism [START_REF] Josz | Moment/sum-of-squares hierarchy for complex polynomial optimization[END_REF][START_REF] Gilbert | Plea for a semidefinite optimization solver in complex numbers[END_REF]. Direct calculation shows that, for M ∈ C m×n and x ∈ C n , there holds

T(M x) = J(M ) T(x). (2.3)

R-injectivity

The notion of R-injectivity will appear in the proof of the necessary and sufficient conditions characterizing an R-linear system of equations that can be transformed into an equivalent C-linear system of the same order (section 3.4).

Definition 2.1 (R-injectivity) A complex matrix M ∈ C m×n is said to be R-injective if any real vector α ∈ R n satisfying M α = 0 vanishes.
Taking the point of view of real linear algebra, the notion of R-injectivity of M ∈ C m×n is equivalent to the injectivity of the real matrix T(M ), while, by (2.3), the injectivity of M is equivalent to the injectivity of the larger real matrix J(M ). Obviously, an injective matrix is R-injective, but the converse does not necessarily hold (unless the matrix is real). For example, the

1 × 2 matrix 1 i (2.4) is R-injective but not injective.
Suppose that an R-injective matrix M ∈ C m×(2n) has an even number of columns (this case is simply easier to discuss, but we will see in the proof of proposition 2.9 that an extension of the result below to a matrix with an odd number of columns is straightforward). Then, it is clear from a real linear algebra argument that one can remove 2(mn) rows from the (2m) × (2n) injective real matrix T(M ), while preserving the injectivity of the resulting matrix. Now these 2(mn) rows of T(M ) are not necessarily the real and imaginary parts of mn rows of M . In other words, it is not true that one can necessarily eliminate mn rows from an R-injective matrix M and keep the R-injectivity of the resulting matrix. To justify this assertion, consider the case of a (2n) × (2n) nonsingular real matrix M . Considered as a complex matrix, M is R-injective, but none of its rows can be removed without destroying its R-injectivity (actually, the 2n rows that can be removed from T(M ) are those of the zero matrix ℑ(M )). Nevertheless, proposition 2.8 below shows that one can find a matrix H ∈ C n×m , which we call a row reduction matrix, such that the complex matrix HM ∈ C n×(2n) is R-injective (the letter H is chosen since the matrix H is "horizontal"; it has less rows than columns, see point 2 of lemma 2.2). This result will be useful in the proof of proposition 3.8.

As an example, consider the 2 × 2 nonsingular real matrix (m = 2 and n = 1 with the notation of the previous paragraph)

M := 1 1 1 -1 . (2.5)
This matrix is R-injective but none of its rows can be removed while preserving the Rinjectivity. Now if that matrix M is left-multiplied by

H := 1 2 1 + i 1 -i ∈ C 1×2 , (2.6)
one gets the R-injective matrix HM given in (2.4). Clearly, the complex nature of HM plays an important role to get that R-injectivity property. Below, the matrix H ∈ C n×m is computed by an iterative algorithm, algorithm 2.7, whose logic is now presented step by step, throughout its first iteration.

Algorithm description

The easiest way of getting an R-injective matrix HM , from an R-injective matrix M , with as few rows as possible, would be to choose a matrix H that selects rows from M , while preserving its supposed R-injectivity. We know, however, from the example (2.5), that this is not always possible. Nevertheless, it seems reasonable to start by getting rid of the superfluous rows of M . The next lemma shows that keeping from the rows of M as many C-linearly independent rows as possible (hence rank(M ) of them) results in a matrix M R : that shares with M the same R-injectivity property. The algorithm below starts by using that technique at each iteration on the considered matrix. Lemma 2.2 (getting rid of superfluous rows) Let M ∈ C m×(2n) and R ⊂ [1 : m] be such that r := |R| is the rank of M . Then

1) M is R-injective if and only if M R : is R-injective, 2) if M is R-injective, then n r 2n and m n. Proof. 1) [⇒] By the property of R, there holds N (M R : ) = N (M ). It results that if M R : α = 0 for some α ∈ R 2n , then M α = 0, implying that α = 0 by the R-injectivity of M . [⇐] Straightforward and true whatever is the nonempty index set R ⊂ [1 : m].
2) One always has r 2n, since the rank of M is less than the number of its columns. Suppose now that M is R-injective. Then, M R : is R-injective by point 1. Hence, the real matrix T(M R : ) ∈ R (2r)×(2n) is injective, implying that r n. Finally, since the rank r does not exceed the number m of rows of the matrix, there must hold m n.

Let M ∈ C m×(2n) be an R-injective matrix. By the second point of the previous lemma, for H ∈ C p×m , the smallest number p of rows of HM ∈ C p×(2n) that is compatible with its R-injectivity is n. Proposition 2.8 below shows that it is indeed possible to find an H ∈ C n×m such that HM is R-injective.

Observation 2.3 At this point and with the set of indices R ⊂ [1 : m] of cardinality r := |R| defined in the previous lemma, as far as the determination of a row reduction matrix H is concerned, three situations are easy to deal with. 1) If r < n, M is not R-injective (point 2 of lemma 2.2). This situation occurs for the 1 × 2 matrix M = 0 0 . 2) If r = n, let H := (I m ) R : be the selector of the rows of M with index in R. Then HM = M R : has the desired dimension n × (2n) and is R-injective if and only if M is R-injective (point 1 of lemma 2.2), a fact that can be easily detected by examining the rank of T(M R : ). This situation occurs for the 1 × 2 matrices M = 1 1 , which is not R-injective, or M = 1 i , which is R-injective. 3) If r = 2n, the matrix M R : is nonsingular, and one can set

H = J(M R : ) -1 0 [1 : n],D ∈ C n×m ,
where J ∈ C n×(2n) is an arbitrary R-injective matrix, for instance, J := I n iI n , D := [1 : m] \ R, and 0 [1 : n],D is the zero n × (m -2n) matrix whose columns are labeled by the indices of D. Then HM = J is indeed an R-injective matrix with the appropriate dimensions. In this computation, we have assumed that the rows of M R : and the columns of (M R : ) -1 are labeled with indices in R ⊂ [1 : m]; the same convention is made below. This situation occurs for the 2 × 2 matrix (2.5) and the row reduction matrix H given by (2.6) to get the R-injective matrix (2.4) is the one given above.

Since r 2n (the rank of M is less than its number of columns), we still have to show how to compute the row reduction matrix H, if any, when n < r < 2n. Algorithm 2.7 below works now in the real space by considering the real matrix T(M R : ) ∈ R (2r)×(2n) and by selecting from it as many linearly independent rows as possible. This number is necessarily 2n, since the matrix has 2n columns.

Observations 2.4 1) If the number of linearly independent rows of T(M R : ) is < 2n, then M is not R-injective. Indeed, then T(M R : ) is not injective (since it has more columns than rows), so that M R : is not R-injective (by definition or so) and M is not R-injective either (by point 1 in lemma 2.2). This situation occurs for the rank 3 matrix

M =   1 0 1 0 0 i 0 i 1 0 i 0   ,
which is not R-injective (the real vector 0 1 0 -1 T is in its null space).

2) Otherwise, the number of linearly independent rows of T(M R : ) is 2n and that matrix is injective, implying that M R : is R-injective (by definition or so), so that M is also R-injective (by point 1 in lemma 2.2). This situation occurs for the rank 3 matrix

M =   1 0 1 0 0 1 0 i 1 0 i 0   , (2.7)
which is R-injective by its last two rows.

It remains to consider the case when 2n linearly independent rows of the real matrix T(M R : ) have been selected. In that case, M is R-injective (observation 2.4(2)) and we pursue in order to show that, in that case, one can also determine a row reduction matrix H ∈ C n×m . The 2n selected linearly independent rows of T(M R : ) can be gathered in a square matrix of order 2n, whose rows can be partitioned as follows

    ℜ(M S c : ) ℑ(M S c : ) ℜ(M S r : ) ℑ(M S i : )     ∈ R (2n)×(2n) , (2.8)
where S c , S r , and S i are disjoint subsets of indices of R: r S c is the set of indices of the rows of M whose real and imaginary parts are selected, r S r is the set of indices of the rows of M whose only real part is selected, and r S i is the set of indices of the rows of M whose only imaginary part is selected.

Observations 2.5 1) If S r = S i = ∅, then |S c | = n
and one can conclude by taking as row reduction matrix the row selector

H = (I m ) S c : ∈ C n×m . Indeed, HM = M S c : ∈ C n×(2n) is R-injective (since T(M S c :
) is injective). This situation occurs for the matrix M in (2.7) when one takes S c = {2, 3}. 2) For the consistency of algorithm 2.7 below, it is important to observe that, at this point, one has S c = ∅, since otherwise one would have r = |R| |S r ∪ S i | = 2n, while it is supposed at this point that r < 2n.

When S r ∪ S i = ∅, point 1 of observation 2.5 has shown that the row indices in the nonempty set S c are good indices to select. For this reason, even when S r ∪ S i = ∅, algorithm 2.7 below collects them at each iteration in a set of row indices denoted by S + , which is initially empty:

S + in updated into S + ∪ S c .
The key point of the recursion lies in the decision taken with respect to the rows with index in S r ∪ S i . Algorithm 2.7 below returns to the complex space with a matrix having a number of rows m + , which is < r m, and a number of columns 2n + , which is < 2n, namely the matrix

M + := M S r ∪S i Z ∈ C m + ×(2n + ) , (2.9)
where

m + := |S r ∪ S i | < |S c ∪ S r ∪ S i | |R| = r m, n + := n -s < n since s := |S c | = 0 (observation 2.5(2)
), and Z ∈ R (2n)×(2n + ) has its columns forming a basis of the null space of the real surjective matrix

T(M S c : ) = ℜ(M S c : ) ℑ(M S c : ) ∈ R (2s)×(2n) .
The next lemma gives some properties of M + .

Lemma 2.6 (properties of M + ) The matrix M + defined above is of order 2n + and R-injective.

Proof. In view of the matrix in (2.8), there holds

m + = |S r ∪S i | = 2n-2|S c | = 2(n-s) = 2n + , so that M + is indeed square.
To prove that the matrix M + is R-injective, suppose that M + α = 0 for some α ∈ R 2n + . Since Zα is a real vector it is also in the null space of ℜ(M S r ∪S i ) and ℑ(M S r ∪S i ), hence in the null space of the matrix in (2.8) (we use the definition of Z). Since, when M + is defined, this last matrix is nonsingular, it follows that Zα = 0 and therefore α = 0 by the injectivity of the real matrix Z.

However, M + may have a rank strictly between in n + and 2n + (this is the case of the example given in section 2.5), so that it is difficult to conclude right now, using observation 2.3 on the matrix M + instead of M . For this reason, the process presented so far, which was applied to M and constitutes the first iteration of algorithm 2.7 below, is now applied to M + . There is some simplification in the subsequent iterations, since we already know that the considered matrices are square and R-injective (lemma 2.6). Now, because the size of these matrices strictly decreases at each iteration, the recursion does not cycle. Actually, the number of iterations does not exceed n (since n + < n), but may reach that number, as shown by the example in section 2.5.

The relevance of the formula (2.9) of the matrix M + may look obscure at this stage of the algorithm description. Its interest may be partially revealed by looking at how a matrix H + ∈ C n + ×m + that would be determined in the second iteration to make H + M + R-injective can be used to determine H ∈ C n×m to make HM R-injective. The role of Z will be highlighted in passing. Suppose indeed that H + M + is R-injective for some

H + ∈ C n + ×m + . We claim that HM is R-injective, when H is defined by H := (I m ) S c : H+ ∈ C n×m ,
where the nonzero columns of H+ ∈ C n + ×m are those of H + (the columns of H + will be labeled with indices taken in [1 : m] to identify the rows of M that they multiply). To see this, suppose that HM α = 0 for some α ∈ R 2n . This implies that (I m ) S c : M α = 0 and H+ M α = 0, or equivalently that M S c : α = 0 and H + M S r ∪S i α = 0. By the first identity, α is a real vector in the null space of M S c : , which is therefore in the null space of T(M S c : ) or, by construction, in the range space of Z. We have shown that α = Zα + for some α + ∈ R 2n + . By the second identity, we now have

0 = H + M S r ∪S i α = H + M S r ∪S i Zα + = H + M + α + . Since H + M + is R-injective and α + is a real vector, it follows that α + = 0 and finally α = 0, proving that HM is R-injective.
The first iteration of algorithm 2.7 has now been completely described and motivated, and its sound link with the second iteration has been partly clarified. We still have to show that the full process works properly, which is the goal of the proof of proposition 2.8 below. It is now time to describe the complete algorithm, through its kth iteration. The only difference with the first iteration is on the way the information is collected along the kth iteration.

Algorithm 2.7 (row reduction of an R-injective matrix) Let be given an m × (2n) complex matrix M , with m n 1. The algorithm terminates either by detecting that M is not R-injective or by finding a matrix

H ∈ C n×m such that HM ∈ C n×(2n) is R-injective (in which case M is R-injective). Set k := 1, M 1 := M , m 1 := m, n 1 := n, and S + 1 := ∅.
We describe the kth iteration of the algorithm. It starts with the matrix

M k ∈ C m k ×(2n k ) , which is R-injective if and only if M is R-injective,
M k . Select a row index set R k ⊂ L k with |R k | = r k such that (M k ) R k : is surjective.
2. First possible terminations.

2.1. If k = 1 and r k < n k , stop (M is not R-injective). 2.2. If r k = n k , there are two subcases. (a) If k = 1 and (M k ) R k : is not R-injective, stop (M is not R-injective).
(b) Otherwise, stop (M is R-injective and one can take as searched row reduction matrix

H := (I m ) (S + k ∪R k ) : . 2.3. If r k = 2n k [here (M k ) R k : is nonsingular], stop (M is
R-injective and one can take as searched row reduction matrix

H := (I m ) S + k : Hk , (2.10)
where Hk is the matrix in C n k ×m with zero columns in addition to those of

H k := J k (M k ) R k : -1 0 [1 : n k ],D k ∈ C n k ×m k , (2.11)
where

J k := I n k iI n k ∈ C n k ×(2n k ) and D k := L k \ R k ).

Selecting rows in the real space

[here n k < r k < 2n k ]. Select rank(T((M k ) R k : )) linearly independent rows of the (2r k ) × (2n k ) real matrix T((M k ) R k : ). 3.1. If k = 1
and the selection has a number of rows < 2n k , stop (M is not Rinjective).

3.2.

Otherwise, the selection has 2n k rows and can be written

     ℜ((M k ) S c k : ) ℑ((M k ) S c k : ) ℜ((M k ) S r k : ) ℑ((M k ) S i k : )      ∈ R (2n k )×(2n k ) , (2.12)
where S c k , S r k , and S i k are disjointed subsets of indices of R k . Update

S + k+1 := S + k ∪ S c k .
(2.13)

3.3. Let s k := |S c k |. If s k = n k
, stop (M is R-injective and one can take as searched row reduction matrix H := (I m ) S + k+1 : ).

Building the matrix for cycling

[here 0 < s k < n k ]. Let L k+1 := S r k ∪ S i k , m k+1 := |L k+1 |, and
n k+1 := n k -s k . (2.14) Compute a matrix Z k ∈ R (2n k )×(2n k+1 )
, whose columns form a basis of the null space of the matrix

ℜ((M k ) S c k : ) ℑ((M k ) S c k : ) ∈ R (2s k )×(2n k ) (2.15)
and set

M k+1 := (M k ) L k+1 : Z k ∈ C m k+1 ×(2n k+1 ) . (2.16)
To summarize, iteration k of the algorithm starts with a matrix

M k ∈ C m k ×(2n k

Complex space

Real space Complex space

(matrix M k ) (a nonsingular part (new matrix M k+1 ) of T((M k ) R k : ))        (M k ) S c k : (M k ) S r k : (M k ) S i k : (M k ) N k : (M k ) D k :        -→      ℜ((M k ) S c k : ) ℑ((M k ) S c k : ) ℜ((M k ) S r k : ) ℑ((M k ) S i k : )      -→ (M k ) L k+1 : Z k R k := S c k ∪ S r k ∪ S i k ∪ N k L k+1 := S r k ∪ S i k . D k := L k \ R k (2.17)
A precision on the notation: S c k is the nonempty set of row indices that are selected at iteration k and

S + k = S c 1 ∪ • • • ∪ S c k-1
is the cumulated set of selected row indices at the beginning of iteration k. If iteration k is not the last one, at the end of it, the algorithm selects the rows L k+1 := S r k ∪S i k for the next iteration; hence

L 1 := [1 : m] ⊃ L 2 ⊃ • • • ⊃ L k ,
with strict inclusions. More explanations are given in the proof of proposition 2.8.

Existence results

In the next proposition and with regard to the algorithm, the phrase well defined means that the operations made in the algorithm, and the given claims and taken decisions make sense.

Proposition 2.8 (row reduction of an R-injective matrix, even number of columns) Let n and m be two positive integers, satisfying m n 1, and M ∈ C m×(2n) . Then algorithm 2.7 is well defined and either detects that M is not R-injective or constructs a matrix

H ∈ C n×m such that HM ∈ C n×(2n) is R-injective (in which case M is R-injective).
Proof. 1) Preliminaries. Consider the kth iteration of the algorithm, starting with the matrix

M k ∈ C m k ×(2n k ) (M 1 = M , m 1 = m, n 1 = n) and the set of selected row indices S + k (S + 1 = ∅).
There holds m k n k 1, either because this is assumed initially (k = 1) or because m k = 2n k (for k 2, see lemma 2.6). We recall that the rows of M k are labeled like those of M to which they correspond and we denote by

L k ⊂ [1 : m] the set of its row indices (L 1 = [1 : m]); hence the notation (M k ) R k : for R k ⊂ L k makes sense. Let us recall that k 2 =⇒ M and M k are R-injective. (2.18)
The necessary R-injectivity of M once the second iteration is triggered follows from observation 2.4(2). The R-injectivity of M k for k 2 is a consequence of lemma 2.6. The implication (2.18) means, in particular, that the possible lack of R-injectivity of M is detected during the first iteration.

2) Recurrent properties. We want to show by induction that, at the beginning of the kth iteration, M k and S + k satisfy

S + k ∩ L k = ∅ and |S + k | = n -n k , (2.19a
)

H k M k is R-injective ⇐⇒ (I m ) S + k : Hk M is R-injective. ( 2
= ∅, L 1 = [1 : m],
and n 1 = n, so that (2.19a) trivially holds. The equivalence (2.19b) is also trivially verified, since S + 1 = ∅, H1 = H 1 , and M 1 = M . 3) The iteration is well defined. Before proving (2.19) by induction, let us examine each stage of the kth iteration of algorithm 2.7 in order to justify that the algorithm is well defined (the item numbers below refer to the corresponding stage numbers in the algorithm). Doing so, we assume that the induction assumptions (2.19) hold (they have just been shown to hold for k = 1).

Selecting rows in the complex

space. Recall that R k , subset of L k ⊂ [1 : m], is a selection of rows of M k such that |R k | is the rank r k of M k .
This stage requires no more explanation.

2. First possible terminations. We follow the arguments given in observation 2.3. The iterations are interrupted in the following three cases.

2.1. If r 1 < n 1 , then M 1 = M is not R-injective
(a) If (M 1 ) R 1 : is not R-injective, then M = M 1 is not R-injective by point 1 of lemma 2.2. This case is not considered if k > 1, since then M is R-injective by (2.18). (b) If (M k ) R k : is R-injective, then M is also R-injective (either
H k = (I m ) R k ,L k ∈ C n k ×m k , H k M k = (M k ) R k : is R-injective, hence, by (2.19b), (I m ) S + k : Hk M = (I m ) (S + k ∪R k ) : M is R-injective. Using (2.19a) and R k ⊂ L k , one gets |S + k ∪R k | = |S + k |+|R k | = (n -n k ) + n k = n, so that H := (I m ) (S + k ∪R k ) :
is in C n×m and is the searched row reduction matrix.

If r

k = 2n k , (M k ) R k :
is indeed square of order 2n k and nonsingular since surjective by the linear independence of its rows. Let H and H k given by (2.10) and (2.11). Then

H k M k = J k is R-injective. By (2.19b
), HM is R-injective, so that H is the searched row reduction matrix.

If the situations given above are not encountered, then necessarily n k < r k < 2n k , since the rank r k of M k does not exceed its number of columns 2n k .

3.

Selecting rows in the real space. At this stage, one selects rank(T((M k ) R k : )) linearly independent rows of the (2r k )×(2n k ) real matrix T((M k ) R k : ). We follow the arguments given in observations 2.4 and 2.5.

If this selection has a number of rows

< 2n k , then (M k ) R k : is not R-injective (observation 2.4(1)
) and therefore M k is not R-injective either (lemma 2.2). By (2.18), this case can only occur when k = 1, in which case M = M 1 is not R-injective.

3.2.

Otherwise, the number of selected rows is 2n k and the selected submatrix (2.12) of T((M k ) R k : ) is nonsingular.

If s

k := |S c k | = n k , then S r k ∪ S i k =
∅ and one can conclude by following the observation 2.5 [START_REF] Gantmacher | Théorie des Marices[END_REF]. One takes

H k := (I m ) S c k ,L k ∈ C n k ×m k , so that H k M k = (M k ) S c k : ∈ C n k ×(2n k ) is R-injective (since T((M k ) S c k : ) is injective
| = |S + k ∪ S c k | = |S + k | + |S c k | = (n -n k ) + s k = n -n k+1
, by the induction assumption (2.19a) and (2.14).

r Consider (2.19b). Let H k+1 ∈ C n k+1 ×m k+1 be an arbitrary matrix, whose columns are labeled like those of M k+1 , with indices in L k+1 .

[⇒] Assume that H k+1 M k+1 is R-injective and that

(I m ) S + k+1 : Hk+1 M α = 0, (2.20)
for some α ∈ R 2n . It suffices to show that α = 0. From (2.20) and (2.13), there hold

(I m ) S + k+1 : M α = M S + k+1 : α = 0 and S + k+1 = S c 1 ∪ • • • ∪ S c k .
(2.21)

We claim and prove by induction that

α = Z 1 • • • Z k α k , for some α k ∈ R 2n k+1 . ( 2

.22)

• Let us start by showing that α = Z 1 α 1 for some α 1 ∈ R 2n 2 . This is because S c 1 ⊂ S + k+1 by the second identity in (2.21) and therefore ℜ(M S c 1 : )α + iℑ(M S c 1 : )α = M S c 1 : α = 0 by the first identity in (2.21). Since α is a real vector, it follows from this last identity that ℜ(M S c 1 : )α = ℑ(M S c 1 : )α = 0. Therefore α is in the null space of the matrix in (2.15) with k = 1. This implies that α = Z 1 α 1 for some α 1 ∈ R 2n 2 .

• Suppose now that, for some positive integer j k-1, there holds α = Z 1 • • • Z j α j with some α j ∈ R 2n j+1 (it is true for j = 1 by the previous point). We then show that α = Z 1 • • • Z j+1 α j+1 with some α j+1 ∈ R 2n j+2 , which will prove (2.22). Since for l ∈ [1 : j], S c j+1 ⊂ L j+1 ⊂ L l+1 , we have from (2.16): Since α j is a real vector, it follows that ℜ((M j+1 ) S c j+1 : )α j = ℑ((M j+1 ) S c j+1 : )α j = 0, so that α j is in the null space of the matrix in (2.15) with k = j + 1. This implies that α j = Z j+1 α j+1 for some

∀ l ∈ [1 : j] : (M l+1 ) S c j+1 : = (M l ) S c j+1 : Z l . (2.23) Next, ℜ((M j+1 ) S c j+1 : )α j + iℑ((M j+1 ) S c j+1 : )α j = ℜ((M j ) S c j+1 : )Z j α j + iℑ((M j ) S c j+1 : )Z j α j [(2.23) with l = j, Z j real] = (M j ) S c j+1 : Z j α j = M S c j+1 : Z 1 • • • Z j α j [ (2
α j+1 ∈ R 2n j+2 and α = Z 1 • • • Z j+1 α j+1 by induction.
The identity (2.20) also implies that H k+1 M L k+1 : α = 0 or, thanks to (2.22):

0 = H k+1 M L k+1 : Z 1 • • • Z k α k = H k+1 (M 2 ) L k+1 : Z 2 • • • Z k α k = • • • = H k+1 M k+1 α k .
Since, by assumption, H k+1 M k+1 is R-injective and since α k is a real vector, it follows that α k = 0, hence α = 0 by (2.22).

[⇐] Assume now that the matrix

(I m ) S + k+1 : Hk+1 M is R-injective (2.24)
and that H k+1 M k+1 α = 0 for some α ∈ R 2n k+1 . It suffices to show that α = 0. Using (2.16) and the inclusions

L k+1 ⊂ L k ⊂ • • • ⊂ L 1 = [1 : m], we get 0 = H k+1 M k+1 α = H k+1 (M k ) L k+1 : Z k α [(2.16)] = ( Hk+1 ) : L k M k Z k α [( Hk+1 ) : (L k \L k+1 ) = 0 and ( Hk+1 ) : L k+1 = H k+1 ] = ( Hk+1 ) : L k (M k-1 ) L k : Z k-1 Z k α [(2.16)] = ( Hk+1 ) : L k-1 M k-1 Z k-1 Z k α [( Hk+1 ) : (L k-1 \L k ) = 0] = ( Hk+1 ) : L k-2 M k-2 Z k-2 Z k-1 Z k α [induction] = • • • = Hk+1 M Z 1 • • • Z k α [induction, M 1 = M , and L 1 = [1 : m]]. ( 2

.25)

This indicates that Z 1 • • • Z k α is a good candidate to be a real vector in the null space of the matrix in (2.24). For this reason, we want to show that

(I m ) S + k+1 : M Z 1 • • • Z k α = 0 (2.26)
or, equivalently since

S + k+1 = S c 1 ∪ • • • ∪ S c k , that ∀ j ∈ [1 : k] : (I m ) S c j : M Z 1 • • • Z k α = 0. (2.27)
For any j ∈ [1 : k], there holds

(I m ) S c j : M Z 1 • • • Z k α = (M 1 ) S c j : Z 1 • • • Z k α [stop here if j = 1] = (M 1 Z 1 ) S c j : Z 2 • • • Z k α [M 1 = M ] = ((M 1 ) L 2 : Z 1 ) S c j : Z 2 • • • Z k α [S c j ⊂ L 2 if j 2] = (M 2 ) S c j : Z 2 • • • Z k α [(2.16) with k = 1] = ((M 2 ) L 3 : Z 2 ) S c j : Z 3 • • • Z k α [S c j ⊂ L 3 if j 3] = (M 3 ) S c j : Z 3 • • • Z k α [(2.16) with k = 2] = • • • = (M j ) S c j : Z j • • • Z k α.
Hence, we have shown that

∀ j ∈ [1 : k] : (I m ) S c j : M Z 1 • • • Z k α = (M j ) S c j : Z j • • • Z k α. Now, since (M j ) S c j : Z j = 0
(I m ) S + k+1 : Hk+1 M Z 1 • • • Z k α = 0, so that Z 1 • • • Z k α = 0 by (2.24) (the vector Z 1 • • • Z k α is real
) and α = 0 by the injectivity of the real matrices Z j .

5) Conclusion.

Since the size of the matrices M k considered at each iteration strictly descreases, the algorithm must be interrupted by one of its stopping criteria: either because it finds that the matrix M is not R-injective (in steps 2.1, 2.2(a), and 3.1, only during the first iteration) or because a row reduction matrix H has been found, making HM an R-injective matrix (in steps 2.2(b), 2.3, and 3.3).

Below, we denote by ⌈•⌉ the ceiling operator: ⌈r⌉ = i if the positive real number r is in the interval (i -1, i] for some integer i. Proposition 2.9 (row reduction of an R-injective matrix) Let n and m be two positive integers, and M ∈ C m×n be an R-injective matrix. Then m ⌈n/2⌉ and there is a matrix H ∈ C ⌈n/2⌉×m such that HM ∈ C ⌈n/2⌉×n is R-injective.

Proof. The case when n is even has been considered in proposition 2.8. Suppose now that n = 2n ′ + 1 for some n ′ ∈ N.

Since T(M ) ∈ R (2m)×(2n ′ +1) is injective, there holds 2m 2n ′ +1 or m n ′ +1 = ⌈n/2⌉. Now, since the real matrix T(M ) ∈ R (2m)×(2n ′ +1) is injective with 2m > 2n ′ + 1, one can add a column of real numbers to the real matrix T(M ), while preserving the injectivity of the resulting matrix (a set of 2n ′ + 1 linear independent vectors of R 2m can be extended to a basis of R 2m ). In other words, one can add a column of complex numbers to M to form an R-injective matrix, say M 1 ∈ C m×2(n ′ +1) . Applying proposition 2.8 to M 1 , one gets a matrix H ∈ C (n ′ +1)×m = C ⌈n/2⌉×m , such that HM 1 ∈ C ⌈n/2⌉×2(n ′ +1) is R-injective. Clearly, HM ∈ C ⌈n/2⌉×n is also R-injective.

An example with a maximal number of iterations

In this section, we show that algorithm 2.7 may require n iterations to compute the row reduction matrix H ∈ C n×m of an R-injective matrix M ∈ C m×(2n) . For this, we show that, starting with a matrix M = M (n) ∈ C (2n)×(2n) with n > 1, which is an element of the family of R-injective matrices defined below, an iteration of the algorithm can produce at the end of the iteration the matrix M (n-1) of the same family, without exiting the loop by satisfying one of its possible stopping tests. We say "can produce" and not "produces", since the effect of an iteration depends on various choices (choice of linearly independent rows in steps 1 and 3, and selection of the index sets S c , S r , and S i in step 3.2). The algorithm exits during the iteration dealing with the first matrix of the family, which reads

M (1) := 1 i 1 i ,
and then finds as row reduction matrix the row selector H = (I 2 ) 1 : . Therefore, the algorithm requires n iterations to find a row reduction matrix for M (n) . Before defining the generic matrix M (n) of the family, let us specify 3 more members, namely M (4) , M (3) , and M (2) , which should help following the description below:

M (4) :=              1 i 0 0 0 0 0 0 0 0 0 0 0 0 1 i 0 0 0 0 0 0 1 i 0 0 0 0 0 0 1 i 1 i 0 0 0 0 0 0 1 0 1 0 1 0 1 i 0 0 0 0 1 0 1 i 0 0 1 0 1 0 1 i              , M (3) :=          1 i 0 0 0 0 0 0 0 0 1 i 0 0 0 0 1 i 1 i 0 0 0 0 1 0 1 0 1 i 0 0 1 0 1 i         
, and M (2)

:=      1 i 0 0 0 0 1 i 1 i 0 0 1 0 1 i      .
We have the property that M (n-1) is a submatrix of M (n) . We have surrounded by boxes the submatrix M (3) in M (4) , the submatrix M (2) in M (3) , and the submatrix M (1) in M (2) .

The generic matrix M (n) ∈ C (2n)×(2n) of the family is formed of two blocs

B (n) i ∈ C n×(2n) , i ∈ {0, 1}, with B (n) 0 above B (n) 1 . The matrix B (n)
0 is the Kronecker product of I n and the R-injective matrix J := 1 i ∈ C 1×2 , namely

B (n) 0 := I n ⊗ J =     1 i 0 0 0 • • • 0 0 0 0 0 1 i 0 • • • 0 0 0 • • • • • • • • • • • • • • • • • • • • • • • • • • • 0 0 0 0 0 • • • 0 1 i     , while B (n) 1 is like the matrix B (n)
0 , but with the 0's below the 1's replaced by 1's.

Proposition 2.10 (worse case) When starting with an R-injective matrix M ∈ C m×(2n) with m n 1, algorithm 2.7 may require n iterations to determine a row reduction matrix H ∈ C n×m .

Proof. As said before the proposition statement, it suffices to show that if algorithm 2.7 starts with M (n) , it generates successively M (n-1) , . . . , M (1) without interruption and stops during the nth iteration when it deals with M (1) .

Let k ∈ [1 : n -1], n k := n -k + 1
, and m k := 2n k . It suffices to show that, if the kth iteration of the algorithm starts with the matrix and set of selected row indices

M (n-k+1) = M (n) [k : n]∪[n+k : 2n],[2k-1 : 2n] ∈ C m k ×(2n k ) and S + k = [1 : k -1] (2.28)
(hence S + 1 = ∅), it can generate M (n-k) = M (n) [k+1 : n]∪[n+k+1 : 2n],[2k+1 : 2n] ∈ C m k+1 ×(2n k+1 ) and S + k+1 = [1 : k] (2.29)
as new matrix and new set of selected row indices for starting the iteration k + 1, without exiting the iteration by one of its stopping tests (unless k = n). Recall that the rows of the considered matrix are numbered with the index of the initial matrix M (n) . Let us consider in sequence the steps of the algorithm.

1. Selecting rows in the complex space. The first row of B

(n-k+1) 0

(hence with index k) and B

(n-k+1) 1

(hence with index n + k) are identical. Let us remove the last one from the matrix, hence selecting the rows of M (n-k+1) with index in

R k := [k : n] ∪ [n + k + 1 : 2n].
(2.30)

Let us show that (M (n-k+1) ) R k : is surjective (hence the rank of M (n-k+1) is r k := 2n k -1), by showing the linear independence of its rows. Let

β := {β i } i∈R k ⊂ C 2n k -1 be such that i∈R k β i M (n-k+1) i : = 0.
By the even columns, one deduces that β k = 0 and that

β i + β n+i = 0 for i ∈ [k + 1 : n].
Next, the odd columns taken in reverse order, yield 0 =

β 2n = • • • = β n+k+1 , implying that β = 0.
2. First possible terminations. For this example and k < n, there is no termination at this step, since

n k < r k = 2n k -1 < 2n k . If k = n, the considered matrix is M (1)
, which has a rank r n = n n = 1. There hold R n = {n} and (M n ) Rn : = 1 i . The algorithm stops in step 2.2.b with the row reduction matrix

H = (I 2n ) [1 : n] : . Indeed S + n ∪ R n = [1 : n -1] ∪ {n} = [1 : n]
, by (2.28). 3. Selecting rows in the real space. Let the operator T defined by (2.2) and R k defined by (2.30). Consider the 2(2n k -1) × (2n k ) real matrix T((M (n-k+1) ) R k : ). The real and imaginary parts of the first row (M (n-k+1) ) k : , the real part of (M (n-k+1) ) [k+1 : n] : , and the imaginary part of (M (n-k+1) ) [n+k+1 : 2n] : are the rows of I 2n k , so that the real matrix T((M (n-k+1) ) R k : ) is injective and the selected rows can be

S c = {k}, S r = [k + 1 : n],
and

S i = [n + k + 1 : 2n].
Since T((M (n-k+1) ) R k : ) is injective, case 3.1 does not occur. Using S + k given by (2.28), we see that in step 3.2, one sets S + k+1 to S + k ∪ {k} = [1 : k], which is the set S + k+1 given in (2.29). Finally, since s k = 1, s k = n k and step 3.2 is ineffective (the case when k = n, hence n k = 1, has been dealt with in step 2 above, with an interruption of the algorithm).

4.

Building the matrix for cycling. Since the columns of the matrix

Z k = 0 2×2n k+1 I 2n k+1 ∈ R (2n k )×(2n k+1 ) ,
form a basis of the null space of the matrix

ℜ((M (n-k+1) ) k : ) ℑ((M (n-k+1) ) k : ) = I 2 0 2×(2n k+1 ) ∈ R (2s k )×(2n k ) , (2.31)
the new matrix is given by

(M (n-k+1) ) ([k+1 : n]∪[n+k+1 : 2n]) : Z k = (M (n-k+1) ) ([k+1 : n]∪[n+k+1 : 2n]),[2k+1 : 2n] = M (n-k) ,
as claimed at the beginning.

This concludes the proof.

3 Solving an R-linear complex system

Motivation

A linear system encountered in the primal-dual interior-point algorithm of [2; section 5.3] for solving the complex semidefinite optimization problem has the form

M x + N x = p, (3.1)
where M and N ∈ C n×n (for some positive integer n), the right-hand side p ∈ C n is given, and the unknown x ∈ C n appears together with its conjugate x in the system. In [START_REF] Gilbert | Plea for a semidefinite optimization solver in complex numbers[END_REF], the matrices M and N have addition properties (M is Hermitian positive definite and N is symmetric) that are not assumed here, so that the method discuss below can be applied in a more general context.

Applying the operator T defined by (2.1) to both sides of (3.1) and using (2.3) allow us to transform the R-linear system (3.1) into the linear system in real numbers (direct calculation is also possible)

ℜ(M ) + ℜ(N ) -ℑ(M ) + ℑ(N ) ℑ(M ) + ℑ(N ) ℜ(M ) -ℜ(N ) T(x) = T(p), (3.2)
which is of size 2n in the real variable T(x) ∈ R 2n . This system can be solved by Gaussian elimination, with a computing time whose dependence in n 3 can be estimated at

1 3 (2n) 3 (a R + p R ) = 8 3 n 3 (a R + p R ), (3.3)
where a R and p R are the computing times for the addition and product of two real numbers.

To get that estimate, we have used algorithm 3.2.1 in [START_REF] Golub | Matrix Computations[END_REF]. The goal of this section is to give necessary and sufficient conditions ensuring that, whatever is p ∈ C n , the solutions to (3.1) are exactly those of the following C-linear system of order n:

Ax = Bp + Cp, (3.4)
where A, B, and C ∈ C n×n (proposition 3.6). Then, the systems (3.1) and (3.4) are said to be equivalent. We also give necessary and sufficient conditions on M and N ensuring the existence of A, B, and C such that the systems (3.1) and (3.4) are equivalent (proposition 3.8). The interest of (3.4) over (3.2) may be theoretical or based on computational reasons. The latter interest comes from the fact that (3.4) can be solved by Gaussian elimination with a computing time whose dependence in n 3 is half the one given by (3.3):

1 3 n 3 (a C + p C ) = 4 3 n 3 (a R + p R ), (3.5)
where a C and p C are the computing times for the addition and product of two complex numbers (we have used the fact that a C = 2 a R and p C = 2 a R + 4 p R for the standard rules of calculation). The computational interest of the approach that solves (3.4) instead of (3.1) now rests on the fact that the computation of A, B and C forming the system (3.4) can be done in a time significantly smaller than the time to solve the system (3.4) itself. It may also be the case that the expensive part of the computation of A, B, and C has to be done for other reasons, in which case solving (3.4) instead of (3.1) becomes attractive computationally. This question is again discussed in the paragraph before proposition 3.4.

Existence and uniqueness

Before determining conditions ensuring the equivalence of the systems (3.1) and (3.4), let us highlight conditions that ensure that (3.1) has a (possibly unique) solution. The obtained results will be useful in the next sections.

The first proposition makes a link between a solution x to the R-linear (3.1) and a solution (x, y) to the C-linear linear system of double dimension

M N N M x y = p p , (3.6)
where the first row is the system (3.1), provided y plays the role of x. Then the second row is the conjugate of (3.1). The matrix of this linear system is denoted by

M := M N N M . (3.7)
Since (p, p) is also in R(M), we see by adding and subtracting (p, p) and (p, p) that (α, α) ∈ R(M) and (α, -α) ∈ R(M) for all α ∈ R n . Adding and subtracting (α, α) and (α, -α), we deduce that (α, 0) ∈ R(M) and (0, α) ∈ R(M) for all α ∈ R n . Therefore all the basis vectors (0, . . . , 0, 1, 0, . . . , 0) of C n are in the range space of M, implying that M is surjective, hence nonsingular.

[Last claim] When (x, y) is the solution to (3.6), (x + y)/2 is the solution to (3.1) (proposition 3.1). Hence, (x + y, x + y)/2 is a solution to (3.6) (proposition 3.1). By the uniqueness of this one, there must hold (x + y)/2 = x, hence y = x. Remarks 3.3 If (3.1) has a unique solution, whatever is p, the same property holds for the R-linear system M x -N x = p, since after multiplication by i, it becomes M (ix) + N (ix) = ip. In the same vein and with the same argument:

{h : M h + N h = 0} = {0} ⇐⇒ {h : M h -N h = 0} = {0}
This "multiplication by i" technique will be used many times.

Equivalence to a C-linear system (nonsingular matrix)

In this section, we show that the R-linear n × n system (3.1) is equivalent to a C-linear n × n system of the form (3.4) in the particular case where both M and M -N M -1 N are nonsingular (by symmetry, the same conclusion holds when N and N -M N -1 M are nonsingular; see remark 3.5( 2)). We will see in the next proposition that, in this case, the solution to the two systems (3.1) and (3.4) is unique, whatever is p. These conditions are encountered in algorithm 5.1 in [START_REF] Gilbert | Plea for a semidefinite optimization solver in complex numbers[END_REF], under a standard regularity assumption [2; proposition 5.5]. More precisely, a link is established between the R-linear system (3.1) and the C-linear system in x,

M -N M -1 N x = p -N M -1 p. (3.8)
This system is in the form (3.4), with A := M -N M -1 N , B := I, and C := -N M -1 . We will see in remark 3.9(3) that, when M and M -N M -1 N are nonsingular, this is the unique system of the form (3.4) equivalent to (3.1), up to a left multiplication of each of its sides by the same nonsingular matrix. In all generality, the computation of the matrices A := M -N M -1 N and C := -N M -1 may require a significant amount of time that destroys the interest of the reduced size of the C-linear system (3.4). Nevertheless, if M is cheap to inverse (because M is diagonal, for example) and N M -1 N can be computed in O(n 2 ) operations (because N is a band matrix, for instance), the computation of A and C can cost only O(n 2 ) operations, in which case the interest of (3.8) over the real system (3.2) becomes clear from the computation cost estimation of section 3.1. Therefore, the computational interest of the equivalent C-linear system (3.4) or (3.8) is case dependent. Proposition 3.4 (existence and uniqueness when M is nonsingular) Let M By the second identity in (ii), BN x + CM x = 0, which is added to the displayed identity above to yield B(M xp + N x) + C(N xp + M x) = 0.

Since B and C act on vectors that are conjugate to each other, the last identity in (ii) implies that these vectors vanish: M x + N x = p, which is (3.1).

3) [(ii) ⇒ (3.11a)] By writing p = α + iβ for arbitrary α and β ∈ R n in the last condition of (ii), we see that (B + C)α + i(B -C)β = 0 implies that α = β = 0, which expresses the fact that the n ′ ×(2n) matrix B + C i(B -C) is R-injective. In particular, n ′ n must hold (point 2 of lemma 2.2).

4) [(i) ⇒ (3.11b)] Since h ∈ N (N ) if and only if N h = 0, the set {h : M h + N h = 0} always contains N (M ) ∩ N (N ), so that we only have to prove the reverse inclusion to get the first equality. Let h be such that M h + N h = 0. Then h is a solution to (3.1) with p = 0. By (i), Ah = 0, hence also A(ih) = 0, so that ih is solution to (3.4) with p = 0.

By (i) again, it follows that M (ih) + N (ih) = 0, implying that M h -N h = 0. Therefore M h = N h = 0.
Let us now show that {h : M h + N h = 0} = N (A). There holds M h + N h = 0 if and only if h is a solution to (3.1) with p = 0, or equivalently by (i), if and only if h a solution to (3.4) with p = 0, which reads Ah = 0. Remarks 3.7 1) Taking C = 0 in proposition 3.6, we see that the R-linear system (3.1) has the same solution set as the simpler C-linear system Ax = Bp, whatever is p ∈ C n , if and only if N = 0, B is injective, and A = BM.

The crucial information in these conditions is that N must vanish to have the equivalence between (3.1) and Ax = Bp.

Similarly, taking B = 0 in proposition 3.6, we see that the the R-linear system (3.1) has the same solution set as the simpler C-linear system Ax = Cp, whatever is p ∈ C n , if and only if M = 0, C is injective, and A = CN.

2) The first identity in (3.11b) is equivalent to saying that {h : M h + N h = 0}, which is the null space of the R-linear operator h → M h + N h, hence an R-linear subspace, is actually a C-linear subspace (a stronger property). It is the argument used in the fourth part of the previous proof.

x 1 = p 1 = p 2 . Now {M x+N x : x ∈ C 2 } = {(x 1 , x 1 ) : x ∈ C 2 }, which is not a C-linear subspace because i(x 1 , x 1 ) = (ix 1 , ix 1 ) is not in that set when x 1 = 0.
Given the matrices M and N ∈ C n×n , the previous proposition does not say much about the existence of matrices A, B, and C ∈ C n×n such that the systems (3.1) and (3.4) are equivalent. Nevertheless, it gives on M and N the necessary condition that is the first identity in (3.11b). The next proposition shows that this is actually also a sufficient condition for finding square matrices A, B, and C ∈ C n×n such that (3.1) and (3.4) are equivalent. Proof. [(i) ⇒ (ii)] This is the implication "(i) ⇒ (3.11b)" of proposition 3.6.

[(ii) ⇒ (i)] By the implication "(ii) ⇒ (i)" of proposition 3.6, it suffices to construct matrices A, B, and C ∈ C n×n such that

A = BM + CN , BN + CM = 0, and {p ∈ C n : Bp + Cp = 0} = {0}. (3.14) Let n 0 := dim(N (M ) ∩ N (N )) n. By the rank-nullity theorem dim R N M = dim C n -dim N N M = n -n 0 . (3.15)
Therefore, one can choose B 1 and C 1 ∈ C (n+n 0 )×n such that B 1 C 1 is surjective and

R N M = N B 1 C 1 . (3.16)
Let us show that the (n + n 0 ) × (2n) matrix

(B 1 + C 1 ) i(B 1 -C 1 ) is R-injective (3.17) or equivalently that {p ∈ C n : B 1 p + C 1 p = 0} = {0}. If B 1 p + C 1 p = 0, then (p, p) is in the null space of B 1 C 1 . By (3.16
), there is a x such that p = N x and p = M x.

Taking the conjugate of the last identity and subtracting the first one yield M x -N x = 0 or M (ix) + N (ix) = 0. Therefore M x = 0 by (ii). It results that p = 0. From (3.17) and proposition 2.9, there is a matrix H ∈ C n×(n+n 0 ) such that r next, using proposition 2.9, a matrix H ∈ C n×(n+n 0 ) is computed such that (3.18) holds, r finally, A, B, and C are computed by (3.19). Therefore, knowing M and N ∈ C n×n satisfying (ii), there is a procedure to compute A, B, and C ∈ C n×n satisfying (i).

H (B 1 + C 1 ) i(B 1 -C 1 ) is R-injective. ( 3
2) The matrices A, B, and C in (i) are not uniquely determined when (ii) holds, since the solution set of (3.4) is not modified by a left-multiplication of both its sides by a nonsingular matrix. This fact can also be seen on the conditions in point (ii) of proposition 3.6 that the matrices A, B, and C must satisfy to define a system (3.4) equivalent to (3.1). Now, two sets of matrix triples (A, B, C) satisfying (i) do not necessarily correspond to each other through a left-multiplication by a nonsingular matrix. For example, the matrices M = 0 and N = 0 satisfy (ii) and both (A, B, C) = (0, I, 0) and (A, B, C) = (0, 0, I) satisfy (i), but these triples do not correspond to each other by a nonsingular left-multiplier. See also the special case in the next remark. (3.20) This is the system (3.8) up to the left-multiplication by B. We still have to show that B is nonsingular. This is indeed the case, since otherwise, by the assumed nonsingularity of M -N M -1 N , there would exist an h = 0 such that B(M -N M -1 N )h = 0; the equivalence between (3.20) and (3.1) would then yield M h + N h = 0, which by (ii) would imply that M h = 0, which would be in contradiction with the nonsingularity of M .

4) The transformation of the R-linear system (3.1) into an equivalent C-linear system of the form (3.4), in the sense given in point (i) of the previous proposition, is not always possible, since the condition in point (ii) is not always satisfied. A first counter-example was given in (1.4). Here is another one n = 1 and M = N = 1.

Then {h : M h + N h = 0} = iR, which differs from N (M ) ∩ N (N ) = {0}, so that (ii) does not hold. And, indeed, the pair (x, p) solves M x + N x = p if and only if x ∈ C and p = 2ℜ(x), while these pairs cannot be the solutions to the system Ax = Bp + Cp for some A, B, and C ∈ C, since A should vanish (taking (x, p) = (i, 0) shows that one should have Ai = 0), but then (x, p) = (1, 0) would satisfy Ax = Bp + Cp and not M x + N x = p.

Conclusion

This paper presents two contributions on elementary linear algebra, intertwining real and complex analysis. First, it shows that, given an R-injective matrix M ∈ C m×n , one can find a matrix H ∈ C ⌈n/2⌉×m such that HM ∈ C ⌈n/2⌉×n is R-injective. Second, it analyzes the links between two linear systems of equations in the unknown x ∈ C n , the R-linear system M x + N x = p and the C-linear system Ax = Bp + Cp, providing, on the one hand, necessary and sufficient conditions on M , N , A, B, and C such that these two systems are equivalent (i.e., have the same solution sets whatever is p ∈ C n ) and, on the other hand, necessary and sufficient conditions on M and N for the existence of A, B, and C making the two systems equivalent.

2 2 2 . 1 4 2. 3 2 . 4

 2214324 Row reduction of an R-injective complex matrix 3 Two bijections and one injection . . . . . . . . . . . . . . . . . . . . . 3 2.2 R-injectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algorithm description . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Existence results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 An example with a maximal number of iterations . . . . . . . . . . . . 16 3 Solving an R-linear complex system 18 3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2 Existence and uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Equivalence to a C-linear system (nonsingular matrix) . . . . . . . . . 21 3.4 Equivalence to a C-linear system (general case) . . . . . . . . . . . .

R

  when the scalars are restricted to R). Let [1 : n] := {1, . . . , n} be the set of the first n positive integers. For a matrix M ∈ C m×n , and index sets I ⊂ [1 : m] and J ⊂ [1 : n], M I,J denotes the submatrix of M obtained by selecting the rows with indices in I and the columns with indices in J. We also use the notation M I : := M I,[1 : n] and M : J := M [1 : m],J . The null space of a matrix M ∈ C m×n is denoted by N (M ) := {h ∈ C n : M h = 0} and its range space by R(M ) := {M x ∈ C m :

1 .

 1 and the set of selected row indices S + k ⊂ [1 : m]. The rows of M k are labeled by indices L k ⊂ [1 : m]. If the iteration is not interrupted, M k and S + k are updated into M k+1 and S + k+1 . Selecting rows in the complex space. Let r k be the rank of

  ) and a set of selected row indices S + k ⊂ [1 : m]. It can interrupt the process either because it has detected that the matrix M is not R-injective (steps 2.1, 2.2(a), and 3.1, only during the first iteration) or because a row reduction matrix H has been found (steps 2.2(b), 2.3, and 3.3). If the process is not interrupted, a new matrix M k+1 ∈ C m k+1 ×(2n k+1 ) is computed by (2.16), with m k+1 := |S r k ∪ S i k | < |R k | = r k m k and n k+1 = n ks k < n k , and new set of selected row indices S + k+1 is computed by (2.13). The strict inequalities m k+1 < m k and n k+1 < n k ensure the finite termination of the process. The diagram below summarizes one iteration of the algorithm and should help following its logic (recall that the rows of M k are labeled with indices in L k ⊂ [1 : m]).

  .23) for all l ∈ [1 : (j -1)] and M 1 = M ] = M S c j+1 : α [induction assumption] = 0 [S c j+1 ⊂ S + k+1 and (2.21)].

3 )

 3 Conditions (i)-(ii) of proposition 3.6 do not imply that {M x + N x : x ∈ C n } is a C-linear subspace. Consider indeed the case when )-(ii) holds with (the matrices B and C have been constructed by using the identity (3.16) appearing in the proof of proposition 3.8 below) since (x, p) verifies (3.1) or (3.4) if and only if

Proposition 3 .

 3 8 (NSC on M and N for an equivalence) Let n be a positive integer, and M and N ∈ C n×n . Then the following conditions are equivalent: (i) ∃ A, B, C ∈ C n×n , ∀ p ∈ C n , (3.1) and (3.4) have the same solutions x, (ii) {h : M h + N h = 0} = N (M ) ∩ N (N ).

r

  To prove the third condition in(3.14), suppose that p satisfies Bp + Cp = 0. Then0 = (B + C)ℜ(p) + i(B -C)ℑ(p) = H(B 1 + C 1 )ℜ(p) + iH(B 1 -C 1 )ℑ(p). By (3.18), ℜ(p) = ℑ(p) = 0. Hence p = 0.Remarks 3.9 1) The proof showing that point (ii) implies the existence of matrices A, B, and C in point (i) is constructive:r first one determines matrices B 1 and C 1 ∈ C (n+n 0 )×n , wheren 0 := dim(N (M ) ∩ N (N )), such that B 1 C 1 ∈ C (n+n 0 )×(2n) is surjective and satisfies (3.16),

3 )

 3 When M and M -N M -1 N are nonsingular, a situation considered in proposition 3.4, (3.1) can be uniquely reduced to(3.8) up to a left-multiplication of the two sides of (3.8) by a nonsingular matrix. Indeed, if M and M -N M -1 N are nonsingular the two sides of the identity in condition (ii) reduce to {0} (combine propositions 3.4 and 3.2 for the left-hand side), so that, by condition (i), (3.1) is equivalent to(3.4). By point (ii) of proposition 3.6 or (3.14) and the nonsingularity of M , there must hold C = -BN M -1 and A = B(M -N M -1 N ), so that (3.4) reads B(M -N M -1 N )x = B(p -N M -1 p).

5 )

 5 Even though B 1 and C 1 were chosen to satisfy(3.16) in the second stage of the proof, it is not required that the searched B and C must satisfyR N M = N B C . (3.21) The second identity in (3.14) only requires that the left-hand side be included in the right-hand side of (3.21). This is what is preserved when B 1 and C 1 are left-multiplied by H in (3.19) to get B and C. A trivial example, in which (3.21) is not satisfied, is when M = N = 0. Then, (ii) holds and matrices satisfying (3.14) are A = 0, B = I, and C = 0. Then M x + N x = p and Ax = Bp + Cp are guaranteed to have the same solution sets whatever is p (namely the solution set is C n if p = 0 and ∅ otherwise). Now the left-hand side of (3.21) is {0} × {0}, while the right-hand side is the larger set {0} × C n . 6) If N = 0, condition (ii) holds and (i) is clearly satisfied with A = M , B = I, and C = 0. But C is not forced to be zero. For example, if M also vanishes, one can take A = 0, B = 2I and C = I.

  .19b)In(2.19b), H k ∈ C n k ×m k is an arbitrary matrix, whose columns are labeled by indices of L k , and Hk ∈ C n k ×m is formed of the columns of H k for the indices in L k and additional zero columns for the indices in [1 : m] \ L k . Note that the matrix that left-multiplies M in the right hand side of the equivalence(2.19b) is in C n×m since from (2.14) and by the second identity in(2.19a), which will be proved below,|S + k | + n k = n.It is trivial to check that the induction assumptions (2.19) holds for k = 1. One has S + 1

  by observation 2.3(1). This situation is only possible if k = 1 since otherwise M k is R-injective by (2.18); this is the reason why the additional test k = 1 is used.2.2.If r k = n k , there are two subcases.

  Building the matrix for cycling. Since the (2s k ) × (2n k ) real matrix in (2.15) is surjective, its null space has dimension 2(n ks k ) = 2n k+1 and the number of columns of Z k is indeed 2n k+1 . The size of the matrix M k+1 defined by (2.16) follows.4) Proof of the recurrent properties. After having shown the consistency of all the steps of the algorithm, we still have to show that the recurrent properties(2.19) are satisfied by the matrix M k+1 defined in (2.16) and by S + k+1 defined in (2.13). L k = ∅ by the induction assumption(2.19a) and L k+1 ⊂ L k , so that S + k ∩ L k+1 = ∅, and on the other hand S c k ∩ L k+1 = ∅ since, by construction, S c

	r Consider (2.19a).
	First condition: the index sets S + k+1 = S + k ∪ S c k and L k+1 = S r k ∪ S i k are disjoint, since on the one hand S + k ∩ k is disjoint of S r k =: L k+1 . k ∪ S i Second condition: observe that S + k and S c k are disjoint, since S + k ∩ L k = ∅ by (2.19a) and S c k ⊂ L

). By

(2.19b)

, HM is R-injective for the matrix H left-multiplying M in

(2.19b)

. By (2.13), this matrix H is the given row selection matrix (I m ) S + k+1 : . 4. k ; therefore, |S + k+1

  by the definition of Z j in step 4 of the algorithm, (2.27) and (2.26) follow. By (2.25) and (2.26), we have shown that

  The first condition in(3.14) is the very definition of A in(3.19). To get the second condition in (3.14), use the incllusion "⊂" in (3.16), which can be written B 1 N + C 1 M = 0. Multiplying this last identity to the left by H and using (3.19) yield BN + CM = 0.

.18) Define the n × n complex matrices B := HB 1 , C := HC 1 , and A := BM + CN. (3.19)

We claim that (3.14) holds for this choice of A, B, and C, which will conclude the proof. r r

† INRIA Paris, 2 rue Simone Iff, CS 42112, 75589 Paris Cedex 12, France. E-mail: Jean-Charles. Gilbert@inria.fr.

Acknowledgment

The author thanks Cédric Josz for discussions at an early stage of the conception of this paper.

As far as computational efficiency is concerned, solving (3.6) instead of (3.1) is probably not a good idea, at least as a general procedure, since the former system is defined in complex numbers and has dimension 2n (the order 2n real system (3.2) should usually be preferable). The system (3.6) should therefore be considered as an intermediate object, useful for the clarification of theoretical issues. More precisely, if x is a solution to (3.1), then (x, x) is a solution to (3.6). Conversely, if (x, y) is a solution to (3.6), then (x + y)/2 is a solution to (3.1).

Proof. [(i) ⇒ (ii)] Clear by taking the conjugate of (3.1) and y = x.

[(ii) ⇒ (i)] Let (x, y) be a solution to (3.6). Taking the conjugate of N x + M y = p and adding to M x + N y = p show that (x + y)/2 is a solution to (3.1).

[(ii) ⇔ (iii)] Clear.

The next proposition goes a little further by giving necessary and sufficient conditions for the existence and uniqueness of a solution to (3.1). Proposition 3.2 (existence and uniqueness) Let M and N ∈ C n×n . Then the following conditions are equivalent:

(i) for all p ∈ C n , the system (3.1) has a solution, (ii) for all p ∈ C n , the system (3.1) has a unique solution, (iii) {h : M h + N h = 0} = {0}, (iv) the matrix M is nonsingular.

If theses equivalent conditions hold and if (x, y) is the solution to (3.6), then x is the solution to (3.1) and y = x.

Proof. [(ii) ⇒ (iii)] Clear, since by (ii), h = 0 is the unique solution to M h + N h = 0.

[(iii) ⇒ (iv)] Since M is a square matrix, it suffices to show that its null space reduces to {0}. Assume that (h, k) is in the null space of M, meaning that M h + N k = 0 and N h + M k = 0. Taking the conjugate of the last identity and adding to the first one yield

By the nonsingularity of M, (3.6) has a solution, so that, by proposition 3.1, (3.1) has also a solution. Now if x ′ is another solution to (3.1), h = xx ′ satisfies M h + N h = 0 and therefore (h, h) is in the null space of M. Since, by (iv), this one reduces to zero, h = 0.

[(i) ⇔ (iv)] Since the implications (iv) ⇒ (ii) ⇒ (i) are clear, it suffices to show that (i) ⇒ (iv). Assume that (i) holds. By proposition 3.1, (p, p) ∈ R(M), for all p ∈ C n . and N ∈ C n×n . Suppose that M is nonsingular. Then the following conditions are equivalent:

(i) for all p ∈ C n , the system (3.1) has a unique solution,

Furthermore, a solution to (3.1) is a solution to (3.8). Conversely, when the conditions (i)-(ii) hold, the solution to (3.8) is the solution to (3.1).

Proof. [(i) ⇔ (ii)] By proposition 3.2, condition (i) is equivalent to the nonsingularity of the matrix M defined by (3.7). When M is nonsingular, M has the following factorization:

Hence M is nonsingular if and only if the Schur complement M -N M -1 N or its conjugate M -N M -1 N is nonsingular.

We still have to prove the last two claims. Let p ∈ C n . Suppose first that x is a solution to (3.1). The conjugate of this system can be written M x + N x = p, so that x = M -1 (p -N x), which, injected in (3.1), yields (3.8).

Suppose now that conditions (i)-(ii) hold, so that M is nonsingular by proposition 3.2. Suppose also that x is a solution to (3.8). Introduce the vector y := M -1 (p -N x), so that

where we used (3.8) to get the second identity. Then (y, x) is a solution to (3.6), implying that y = x is a solution to (3.1) by proposition 3.2 and the nonsingularity of M.

Remarks 3.5 1) If M is nonsingular and (3.8) has a solution, but conditions (i)-(ii) of proposition 3.4 do not hold, then there is always a solution to (3.8) that is not a solution to (3.1). Indeed, let x be a solution to (3.8). By the singularity of M -N M -1 N , there is an h = 0 such that (M -N M -1 N )h = 0, so that the set x+Ch is made of solutions to the C-linear system (3.8). We claim that one of the elements of {x, x + h, x + ih}, which are in x + Ch, hence solutions to (3.8), is not a solution to (3.1). Indeed, otherwise, both M h + N h and M h -N h would vanish, hence M h = 0 and h = 0 (by the assumed nonsingularity of M ), contradicting h = 0.

2) The case when N , instead of M , is nonsingular can be dealt with similarly, since the system (3.1) also reads N y + M y = p, (3.10) with y = x, which has the same structure as (3.1).

3) When both M and N are nonsingular, there is no advantage in considering (3.1) or (3.10), in the sense that both matrices M -N M -1 N and N -M N -1 M are nonsingular simultaneous. Indeed, the latter matrix is the conjugate of -M N -1 (M -N M -1 N ).

Equivalence to a C-linear system (general case)

In this section, we study the equivalence between the two systems (3.1) and (3.4), without assuming the nonsingularity of matrices or the uniqueness of solution. Equivalence means that, whatever is p, both systems have the same set of solutions. Necessary and sufficient conditions ensuring this equivalence are given. We start with a proposition that characterizes the matrices A, B, and C, in terms of M and N , that can be used in (3.4) while guaranteeing the equivalence of this system with (3.1). Nothing is said on the existence of these matrices; this will be the subject of proposition 3.8. The next proposition makes no assumption on the number of rows of the matrices A, B, and C, but it happens that this one must necessarily be larger than n. The proposition also gives some consequences of this equivalence, which will be useful below for the construction of the matrices A, B, and C in the proof of proposition 3.8. Furthermore, these conditions imply that Conversely, assume now that x satisfies (3.4). By the first identity in (ii), it follows that BM x + CN x = Ax = Bp + Cp or B(M xp) + C(Nxp) = 0.