# A Note on Solutions of Linear Systems

Authors: Branko Malešević; Ivana Jovović; Milica Makragić; Biljana Radičić
Journal: ISRN Algebra
 (2013)

---

## Abstract

We will consider Rohde's general form of{1}-inverse of a matrix A. The necessary and sufficient condition for consistency of a linear system Ax=c will be represented. We will also be concerned with the minimal number of free parameters in Penrose's formula x=A(1)c+(I-A(1)A)y for obtaining the general solution of the linear system. These results will be applied for finding the general solution of various homogenous and nonhomogenous linear systems as well as for different types of matrix equations.


---

## Body

## 1. Introduction

In this paper, we consider nonhomogeneous linear system inn variables
(1)Ax=c,
where A is an m×n matrix over the field ℂ of rank a and c is an m×1 matrix over ℂ. The set of all m×n matrices over the complex field ℂ will be denoted by ℂm×n, m,n∈ℕ. The set of all m×n matrices over the complex field ℂ of rank a will be denoted by ℂam×n. For simplicity of notation, we will write Ai→ (A↓j) for the ith row (the jth column) of the matrix A∈ℂm×n.Any matrixX satisfying the equality AXA=A is called {1}-inverse of A and is denoted by A(1). The set of all {1}-inverses of the matrix A is denoted by A{1}. It can be shown that A{1} is not empty. If the n×n matrix A is invertible, then the equation AXA=A has exactly one solution A-1, so the only {1}-inverse of the matrix A is its inverse A-1; that is, A{1}={A-1}. Otherwise, {1}-inverse of the matrix A is not uniquely determined. For more information about {1}-inverses and various generalized inverses, we recommend Ben-Israel and Greville [1] and Campbell and Meyer [2].For each matrixA∈ℂam×n there are regular matrices P∈ℂn×n and Q∈ℂm×m such that
(2)QAP=Ea=[Ia000],
where Ia is a×a identity matrix. It can be easily seen that every {1}-inverse of the matrix A can be represented in the form
(3)A(1)=P[IaUVW]Q,
where U=[uij], V=[vij], and W=[wij] are arbitrary matrices of corresponding dimensions a×(m-a), (n-a)×a, and (n-a)×(m-a) with mutually independent entries; see Rohde [3] and Perić [4].We will generalize the results of Urquhart [5]. Firstly, we explore the minimal numbers of free parameters in Penrose's formula
(4)x=A(1)c+(I-A(1)A)y
for obtaining the general solution of the system (1). Then, we consider relations among the elements of A(1) to obtain the general solution in the form x=A(1)c of the system (1) for c≠0. This construction has previously been used by Malešević and Radičić [6] (see also [7] and [8]). At the end of this paper, we will give an application of this results to the matrix equation AXB=C.


## 2. The Main Result

In this section, we indicate how a technique of an{1}-inverse may be used to obtain the necessary and sufficient condition for an existence of a general solution of a nonhomogeneous linear system.Lemma 1.
The nonhomogeneous linear system (1) has a solution if and only if the last m-a coordinates of the vector c′=Qc are zeros, where Q∈ℂm×m is regular matrix such that (2) holds.Proof.
The proof follows immediately from Kronecker-Capelli theorem. We provide a new proof of the lemma by using the{1}-inverse of the system matrix A. The system (1) has a solution if and only if c=AA(1)c; see Penrose [9]. Since A(1) is described by (3), it follows that
(5)AA(1)=AP[IaUVW]Q=Q-1[IaU00]Q.
Hence, we have the following equivalences:
(6)c=AA(1)c⟺(I-AA(1))c=0⟺(Q-1Q-Q-1[IaU00]Q)c=0⟺Q-1[0-U0In-a]Qc︸c′=0⟺[0-U0In-a]c′=0⟺c′=[ca′cn-a′][0-U0In-a][ca′cn-a′]=0⟺[-Ucn-a′cn-a′]=0⟺cn-a′=0.
Furthermore, we conclude that c=AA(1)c⇔cn-a′=0.Theorem 2.
The vector(7)x=A(1)c+(I-A(1)A)y,y∈ℂn×1  is an arbitrary column, is the general solution of the system  (1), if and only if the {1}-inverse A(1) of the system matrix A has the form (3) for arbitrary matrices U and W and the rows of the matrix V(ca′-ya′)+y(n-a)′ are free parameters, where Qc=c′=[ca′/0]T and P-1y=y′=[ya′/yn-a′]T.Proof.
Since{1}-inverse A(1) of the matrix A has the form (3), the solution of the system x=A(1)c+(I-A(1)A)y can be represented in the form
(8)x=P[IaUVW]Qc+(I-P[IaUVW]QA)y=P[IaUVW]c′+(I-P[IaUVW]QAPP-1)y.
According to Lemma 1 and from (2), we have
(9)x=P[IaUVW][ca′0]+(I-P[IaUVW][Ia000]P-1)y.
Furthermore, we obtain
(10)x=P[ca′Vca′]+(I-P[Ia0V0]P-1)[yayn-a]=P[ca′Vca′]+(PP-1-P[Ia0V0]P-1)[yayn-a]=P[ca′Vca′]+P(I-[Ia0V0])P-1[yayn-a]=P[ca′Vca′]+P[00-VIn-a][ya′yn-a′],
where y′=P-1y. We now conclude that
(11)x=P([ca′Vca′]+[0-Vya′+yn-a′])=P[ca′V(ca′-ya′)+yn-a′].
Therefore, since matrix P is regular, we deduce that P[ca′/(V(ca′-ya′)+yn-a′)]T is the general solution of the system (1) if and only if the rows of the matrix V(ca′-ya′)+yn-a′ are n-a free parameters.Corollary 3.
The vector(12)x=(I-A(1)A)y,y∈ℂn×1 is an arbitrary column, is the general solution of the homogeneous linear system Ax=0, A∈ℂm×n, if and only if the {1}-inverse A(1) of the system matrix A has the form (3) for arbitrary matrices U and W and the rows of the matrix -Vya′+y(n-a)′ are free parameters, where P-1y=y′=[ya′/yn-a′]T.Example 4.
Consider the homogeneous linear system(13)x1+2x2+3x3=04x1+5x2+6x3=0.
The system matrix is
(14)A=[123456].
For regular matrices
(15)Q=[10-41],P=[12310-13-2001],
equality (2) holds. Rohde's general {1}-inverse A(1) of the system matrix A is of the form
(16)A(1)=P[1001v11v12]Q.
According to Corollary 3 the general solution of the system (13) is of the form
(17)x=P[000000-v11-v121]P-1[y1y2y3],
where
(18)P-1=[1230-3-6001].
Therefore, we obtain
(19)x=P[000000-v11-v121][y1+2y2+3y3-3y2-6y3y3]=P[00-v11y1-(2v11-3v12)y2-(3v11-6v12-1)y3].
If we take α=-v11y1-(2v11-3v12)y2-(3v11-6v12-1)y3 as a parameter, we get the general solution
(20)x=[12310-13-2001][00α]=[α-2αα].Corollary 5.
The vector(21)x=A(1)c
is the general solution of the system  (1), if and only if the {1}-inverse A(1) of the system matrix A has the form (3) for arbitrary matrices U and W and the rows of the matrix Vca′ are free parameters, where Qc=c′=[ca′/0]T.Remark 6.
Similar result can be found in the paper by Malešević and Radičić [6].Example 7.
Consider the nonhomogeneous linear system(22)x1+2x2+3x3=74x1+5x2+6x3=8.
According to Corollary 5, the general solution of the system (22) is of the form
(23)x=P[1001v11v12]Q[78]=P[7-207v11-20v12].
If we take α=7v11-20v12 as a parameter, we obtain the general solution of the system
(24)x=P[7-20α]=[12310-13-2001][7-20α]=[-193+α203-2αα].
We are now concerned with the matrix equation(25)AX=C,
where A∈ℂm×n, X∈ℂn×k, and C∈ℂm×k.Lemma 8.
The matrix equation (25) has a solution if and only if the last m-a rows of the matrix C′=QC are zeros, where Q∈ℂm×m is regular matrix such that (2) holds.Proof.
If we writeX=[X↓1X↓2⋯X↓k] and C=[C↓1C↓2⋯C↓k], then we can observe the matrix equation (25) as the system of matrix equations
(26)AX↓1=C↓1AX↓2=C↓2⋮AX↓k=C↓k.
Each of the matrix equation AX↓i=C↓i, 1≤i≤k, by Lemma 1 has solution if and only if the last m-a coordinates of the vector C↓i′=QC↓i are zeros. Thus, the previous system has solution if and only if the last m-a rows of the matrix C′=QC are zeros, which establishes that matrix equation (25) has solution if and only if all entries of the last m-a rows of the matrix C′ are zeros.Theorem 9.
The matrix(27)X=A(1)C+(I-A(1)A)Y∈ℂn×k,Y∈ℂn×k is an arbitrary matrix, is the general solution of the matrix equation  (25) if and only if the {1}-inverse A(1) of the system matrix A has the form (3) for arbitrary matrices U and W and the entries of the matrix
(28)V(Ca′-Ya′)+Y(n-a)′
are mutually independent free parameters, where QC=C′=[Ca′/0]T and P-1Y=Y′=[Ya′/Yn-a′]T.Proof.
Applying Theorem2 on each system AX↓i=C↓i, 1≤i≤k, we obtain that
(29)X↓i=P[Ca↓i′V(Ca↓i′-Ya↓i′)+Yn-a↓i′]
is the general solution of the system if and only if the rows of the matrix V(Ca↓i′-Y′a↓i)+Yn-a↓i′ are n-a free parameters. Assembling these individual solutions together we get that
(30)X=P[Ca′V(Ca′-Ya′)+Yn-a′]
is the general solution of matrix equation (25) if and only if entries of the matrix V(Ca′-Ya′)+Yn-a′ are (n-a)k mutually independent free parameters.From now on we proceed with the study of the nonhomogeneous linear system of the form(31)xB=d,
where B is an n×m matrix over the field ℂ of rank b and d is a 1×m matrix over ℂ. Let R∈ℂn×n and let S∈ℂm×m be regular matrices such that
(32)RBS=Eb=[Ib000].
An {1}-inverse of the matrix B can be represented in Rohde's form
(33)B(1)=S[IbMNK]R,
where M=[uij], N=[vij], and K=[wij] are arbitrary matrices of corresponding dimensions b×(n-b), (m-b)×b and (m-b)×(n-b) with mutually independent entries.Lemma 10.
The nonhomogeneous linear system (31) has a solution if and only if the last m-b elements of the row d′=dS are zeros, where S∈ℂm×m is regular matrix such that (32) holds.Proof.
By transposing the system (31), we obtain system BTxT=dT and by transposing matrix equation (32) we obtain that STBTRT=Eb. According to Lemma 1, the system BTxT=dT has solution if and only if the last m-b coordinates of the vector STdT are zeros, that is, if and only if the last m-b elements of the row d′=dS are zeros.Theorem 11.
The row(34)x=dB(1)+y(I-BB(1)),y∈ℂ1×n is an arbitrary row, is the general solution of the system  (31), if and only if the {1}-inverse B(1) of the system matrix B has the form (33) for arbitrary matrices N and K and the columns of the matrix (db′-yb′)M+yn-b′ are free parameters, where dS=d′=[db′|0] and yR-1=y′=[yb′|yn-b′].Proof.
The basic idea of the proof is to transpose the system (31) and to apply Theorem 2. The {1}-inverse of the matrix BT is equal to a transpose of the {1}-inverse of the matrix B. Hence, we have
(35)(BT)(1)=(B(1))T=(S[IbMNK]R)T=RT[IbNTMTKT]ST.
We can now proceed analogously to the proof of Theorem 2 to obtain that
(36)xT=RT[d′bTMT(db′T_-yb′T)+yn-b′T]
is the general solution of the system BTxT=dT if and only if the rows of the matrix MT(db′T-yb′T)+yn-b′T are n-b free parameters. Therefore,
(37)x=[db′∣(db′-yb′)M+yn-b′]R
is the general solution of the system (31) if and only if the columns of the matrix (db′-yb′)M+yn-b′ are n-b free parameters. Analogous corollaries hold for Theorem 11.We now deal with the matrix equation(38)XB=D,
where X∈ℂk×n, B∈ℂn×m, and D∈ℂk×m.Lemma 12.
Matrix equation  (38) has a solution if and only if the last m-b columns of the matrix D′=DS are zeros, where S∈ℂm×m is regular matrix such that (32) holds.Theorem 13.
The matrix(39)X=DB(1)+Y(I-BB(1))∈ℂk×n,Y∈ℂk×n is an arbitrary matrix, is the general solution of the matrix equation (38) if and only if the {1}-inverse B(1) of the system matrix B has the form (33) for arbitrary matrices N and K and the entries of the matrix
(40)(Db′-Yb′)M+Y(n-b)′
are mutually independent free parameters, where DS=D′=[Db′|0] and YR-1=Y′=[Yb′|Yn-b′].


## 3. An Application

In this section we will briefly sketch properties of the general solution of matrix equation(41)AXB=C,
where A∈ℂm×n, X∈ℂn×k, B∈ℂk×l, and C∈ℂm×l. If we denote by Y matrix product XB, then the matrix equation (41) becomes
(42)AY=C.
According to Theorem 9, the general solution of the system (42) can be presented as a product of the matrix P and the matrix which has the first a=rank(A) rows same as the matrix QC and the elements of the last m-a rows are (m-a)n mutually independent free parameters; P and Q are regular matrices such that QAP=Ea. Thus, we are now turning on to the system of the form
(43)XB=D.
By Theorem 13, we conclude that the general solution of the system (43) can be presented as a product of the matrix which has the first b=rank(B) columns equal to the first b columns of the matrix DS and the rest of the columns have mutually independent free parameters as entries, and the matrix R, for regular matrices R and S such that RBS=Eb. Therefore, the general solution of the system (41) is of the form
(44)X=P[GabFHL]R,
where Gab is a submatrix of the matrix QCS corresponding to the first a rows and the first b columns and the entries of the matrices F, H, and L are nk-ab free parameters. We will illustrate this on the following example.Example 14.
We consider the matrix equation(45)AXB=C,
where A=[1-2-24], B=[121121121] and C=[121-2-4-2]. If we take Y=XB, we obtain the system
(46)AY=C.
It is easy to check that the matrix A is of the rank a=1 and for matrices Q=[1021] and P=[1201] the equality QAP=Ea holds. Based on Theorem 9, the equation AY=C can be rewritten in the system form
(47)AY↓1=[1-2],AY↓2=[2-4],AY↓3=[1-2].
Combining Theorem 2 with the equality
(48)[c1′c2′c3′000]=[1021][121-2-4-2]=[121000]
yields
(49)Y↓1=P[1v-vz11+z21︸α],Y↓2=P[22v-2vz12+z22︸β],Y↓3=P[1v-vz13+z23︸γ],
for an arbitrary matrix Z=[z11z12z13z21-z22z23]. Therefore, the general solution of the system AY=C is
(50)Y=P[121αβγ].
From now on, we consider the system
(51)XB=D
for
(52)D=P[121αβγ]=[1+2α2+2β1+2γαβγ].
There are regular matrices R=[100-110-101] and S=[1-2-1010001] such that RBS=Eb holds. Since the rank of the matrix B is b=1, according to Lemma 12 all entries of the last two columns of the matrix D′=DS are zeros; that is, we have γ=α, β=2α. Hence, we get that the matrix D′ is of the form D′=[1+2α00α00]. Applying Theorem 13, we obtain
(53)X=[1+2α(1+2α-t11)m11+t12︸β1(1+2α-t11)m12+t13︸β2α(α-t21)m11+t22︸γ1(α-t12)m12+t23︸γ2]R,
for an arbitrary matrix T=[t11t12t13t21t22t23]. Finally, the solution of the system AXB=C is
(54)X=[1+2α-β1-β2β1β2α-γ1-γ2γ1γ2].



---

*Source: 142124-2013-08-01.xml*