半张量积下矩阵方程组AX=B,XC=D的最小二乘解

李 涛,周学林,李姣芬

(1.桂林电子科技大学数学与计算科学学院广西高校数据分析与计算重点实验室,广西桂林 541004)

(2.桂林电子科技大学教务处,广西桂林 541004)

1 引言

本文中所用记号Rm×n表示所有实数域上m×n阶矩阵的集合;Ik为k阶单位矩阵.对M ∈Rm×n,MT和M†分别表示转置和Moore-Penrose广义逆.对矩阵M,N ∈Rm×n,内积定义为〈M,N〉=trace(MTN),由此导出的矩阵范数为Frobenius范数,记为‖·‖.lcm{m,n}和gcd{m,n}分别表示正整数m,n的最小公倍数和最大公约数.对M=[aij],N=[bij]∈Rm×n,M⊗N 表示矩阵M 和N 的Kronecker积[1]

M⊙N表示矩阵M与N的Hadamard积[1]

对M=[aij]∈Rm×n,矩阵的列拉直算子Vc(·)和行拉直算子Vr(·)分别表示为

定义1[2]给定矩阵A∈Rm×n,B∈Rh×k,记t=lcm{n,h}为n,h的最小公倍数,矩阵A和B的半张量积可表示为

半张量积最初由程代展教授提出用以解决多线性函数的矩阵表示问题[3],随后不仅应用在高维数据的排列以及电力系统非线性鲁棒稳定控制代数化等问题[4],而且为布尔网络[5],密码学[6],图染色[7],模糊控制[8]等领域中的问题研究提供了一种新的研究工具.而这些问题的解决在某些情况下可归结为半张量积下线性方程或矩阵方程的求解问题.如在网络非合作化问题中[9],设有m个玩家,记M={1,2,···,m},玩家j的策略集是N={1,···,nj},j=1,2,···,m.现假定玩家 j 的混合策略是

则所求的Nash 均衡点即等价于求解下列半张量积下的矩阵方程

其中Φ已知.对于此类问题,姚娟等[10]将其归结为半张量积下矩阵方程AX=B求解问题,并细致研究了半张量积下方程该有解的充要条件及具体解析表达式,同时在其博士论文中讨论了半张量积下矩阵方程AX=B的最小二乘解.在实际应用中,如布尔网络,模糊控制及网络非合作化问题中,我们往往会遇见更加复杂的问题,利用半张量积工具,这类问题可归结为如下半张量积下的矩阵方程组

方程(1.1)中的系数矩阵均来自于实测数据,由于测量误差的影响,得到的数据总是不精确的.又由于舍入误差的影响,方程(1.1)不一定满足类似于文[10]给出的较复杂的相容条件,因此有必要讨论如下半张量积下矩阵方程组的最小二乘问题.

问题1给定矩阵A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D∈Rl×d,求X∗∈Rp×q满足

对于矩阵方程(组)的求解及其最小二乘解问题,因其在生物学,工程力学,参数识别,振动理论的逆问题以及线性规划等广泛的应用,故已被广泛研究.众多学者利用矩阵分块,广义逆,矩阵分解等多种技巧方法将方程或方程组降维,进而给出解存在的充要条件及其具体解析表达式,或进一步讨论及最小二乘解及极小范数最小二乘解.如对一般矩阵方程组

Mitra[11]基于广义逆给出了极小秩最小二乘解;李[12–14]分别探究了方程(1.3)的自反解,广义自反解,镜像对称最小二乘解,κ-厄尔米特最小二乘解;裘[15]则利用Kronecker积将其化成相应方程组,再利用广义逆给出解的拉直形式;袁[16]利用矩阵的谱分解给出了最小二乘解和对称最小二乘解的显示表达式.普通矩阵乘积下矩阵方程组(1.3)的求解及其最小二乘解已得到充分研究,但半张量积下矩阵方程组(1.1)未见有研究成果,因此将半张量积概念推广到矩阵方程组的研究工作也是有意义的.类似于文[10]处理半张量下矩阵方程AX=B的研究思路,首先将半张量积下的矩阵方程组转化为普通乘积下的矩阵方程组,进而结合矩阵分块、矩阵广义逆及其矩阵分解技巧给出最小二乘解的具体解析表达式.同样首先考虑矩阵-向量方程,即(1.1)式中X 为向量的情形,研究其最小二乘解的具体解析表达式;进而探究一般形式矩阵-矩阵方程,即(1.1)式中X为矩阵的情形,研究其最小二乘解的具体解析表达式.

本文推导过程中用到如下矩阵微分的基础知识

2 矩阵-向量方程(1.1)的最小二乘解

本节考虑矩阵-向量型的最小二乘问解,即给定矩阵A∈Rm×n,B∈Rh×k,C∈Ra×b,和D∈Rl×d,求向量X∗∈Rp满足

由半张量积定义知,在方程(1.1)中矩阵A与B的行数,矩阵X与D的行数均存在倍数关系.故可分m=h,p=l;m=h,pl;mh,p=l和mh,pl四种情形来考虑问题.经验证m=h,p=l和m=h,pl情况下X∗的解析表达式相同,同样mh,p=l和mh,pl情形下结果类似,故只需从m=h和mh这两种情形下展开讨论.我们的研究思路是,首先利用半张量积的定义将问题转化为普通乘积下的最小二乘问题,再结合矩阵的微分和广义逆给出最小二乘解X∗的具体解析表达式.

2.1 简单形式m=h

由半张量积定义,可得问题(2.1)在m=h情形下有解的必要条件.

引理1若X是问题(2.1)的解,则矩阵A,B,C,D的维数需满足

i)和必为正整数.

ii)b=d并且

证对于

有其中t=lcm{n,p}.由m=h得t=n,进而有必为正整数.对于

有

因此t1=a,并且

从而必为正整数.此外引理得证.

称引理1中的条件为维数相容条件,并假定问题(2.1)满足相容条件.将(2.1)式转化为

其中t1=lcm{n,p},t2=lcm{1,a}.记(2.2)式的目标函数为F(X).此时有

其中As表示矩阵 A 的第 s列,Br表示矩阵B 的第r列,r=1,···,k;s=1,···,n.由一阶微分必要条件知F(X∗)达到极小须对函数F(X)求导,可得

结合广义逆,可得如下结论.

定理1给定矩阵A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D ∈Rl×d,则问题(2.1)在m=h情形下的唯一最小二乘解X∗可表示为

例1令

则由引理1有故X∗∈R3,再由定理1可得

故唯一最小二乘解X∗=[0.0332,0.2373,0.2391]T.

2.2 一般情形mh

由半张量积定义,可得mh时问题(2.1)的维数相容条件.

引理2若X是问题(2.1)的解,则矩阵A,B,C,D的维数须满足

i)必为正整数

证由半张量积的定义有

其中的公约数.此外,

故可知与k互素.若则这显然与条件矛盾.证明完毕.

假定问题(2.1)满足相容条件.由半张量定义,问题(2.1)可转化为

记此时问题(2.4)可转化为m=h情形来讨论,利用上一小节的结论可得

定理2给定矩阵A∈Rm×n,B ∈Rh×k,C ∈Ra×b和D ∈Rl×d,则方程(2.1)在mh情形下的最小二乘解X∗的解析表达式为

其中

表示矩阵的第s列,Br表示矩阵B 的第r列,r=1,···,k;s=1,···,nh/m.

例2令

则由引理2知故最小二乘解X∗∈R3,再由定理2可得

故其唯一最小二乘解X∗=[0.85371.6393−1.1944]T.

3 矩阵-矩阵方程(1.1)的最小二乘解

本节讨论矩阵-矩阵型最小二乘解,即给定矩阵A∈Rm×n,B∈Rh×k,C∈Ra×b和D ∈ Rl×d,求矩阵X ∈ Rp×q使得

仿照第二节,也分m=h,l=p;m=h,lp;mh,l=p和mh,lp四种情况讨论问题.先考虑m=h,l=p的情形,其它情形可类似讨论.由半张量积的定义将(3.1)式转化为普通乘积下的最小二乘问题,进而结合奇异值分解及广义逆给出最小二乘解X∗的解析表达式.为方便记(3.1)式中右端极小值问题中目标函数为G(X).

3.1 简单情形m=h,p=l

引理3若X∈Rp×q是问题(3.1)的解,则系数矩阵A,B,C,D的维数满足下列条件

(ii)且

证对于方程(1.1)有

因为m=h和l=p,则因此并且,均为整数,且有均整除k.

假定问题(3.1)满足引理3中给出的维数相容条件.对于AX=B,有

其中分别是矩阵A,B 的列分块矩阵,t=1,···,q.通过矩阵的列拉直算子Vc(·)将上式转化为

记

对于XC=D,有

记由(3.2)和(3.3)式可得

对G(X)进行求导得

由一阶微分必要条件知,函数G(X∗)达到极小值需因此

记矩阵的奇异值分解为

其中U1=[U11U12],V1=[V11V12],U2=[U21U22],V2=[V21V22]均为列正交矩阵.而Σ1=diag(σ1σ2···σs),Σ2=diag(η1η2···ηt),其中 σi≥ 0,ηj≥ 0(i=1,···,s;j=1,···,t)分别为矩阵的奇异值,

将(3.6)式代入方程(3.5)得

假定

其中矩阵 X11∈ Rs×t,X12∈ Rs×(q−t),X21∈ R(p−s)×t,X22∈ R(p−s)×(q−t).将上述分块代入方程(3.7),方程(3.7)等价于

定理 3给定矩阵A ∈ Rm×n,B ∈ Rh×k,C ∈ Ra×b和 D ∈ Rl×d,则方程 (3.1)在m=h,p=l情形下的最小二乘解X∗的解析表达式为

其中 X22 ∈ R(p−s)×(q−t)任意.

例3令

则根据引理3可得,其最小二乘解X∗∈R2×3,由定理3可知

故最小二乘解

3.2 一般情形m=h,pl

由半张量积定义给出m=h,pl情形下问题(3.1)的维数相容条件.

引理4若X∈Rp×q是问题(3.1)的最小二乘解,则须满足两个条件

证由半张量积的定义有

因为m=h,故β|a,若β=1,则l=p,这与条件矛盾.故而必为整数.并且且证明完毕.

从引理4中可看出其最小二乘解不唯一,令其所有解称为相容解.假定问题4满足引理4中的维数相容条件,则可得下列结果:对于AX=B,其结果类似于3.1小节有

记

其中分别是矩阵A,B 的分块矩阵,t=1,···,q.对于XC=D,有

其中Xi是矩阵X 的第i行,分别是矩阵和矩阵D的分块矩阵 (i=1,···,p;j=1,···,q).通过矩阵的行拉直算子 Vr(·)可将 (3.10)式进一步简化为

简记

则

重复3.1小节中求导的过程可得下述定理.

定理4给定矩阵A∈Rm×n,B∈Rh×k,C∈Ra×b,和D∈Rl×d.A和B 的奇异值分解如(3.6)式所示.则方程(3.1)在m=h,pl情形下的最小二乘解X∗可表示为

其中 X22 ∈ R(p−s)×(q−t)任意.

例4令

则由引理4知,故其最小二乘解X∗∈R2×6,再由定理4得

则可得该方程的最小二乘解为

3.3 一般情形mh,p=l

同样首先给出mh,p=l情形下问题(3.1)的维数相容条件.

引理5若X ∈Rp×q是问题(3.1)的最小二乘解,则须满足

i)必是正整数;

ii)其中α是n和 k的公约数,且

证证明过程类似于引理4.

类似于3.1小节.记则又转化为m=h,p=l的情形.

记

其中重复3.1小节的过程,则有下列结果.

定理5给定矩阵A∈Rm×n,B∈Rh×k,C∈Ra×b和D∈Rl×d.A和B 的奇异值分解如(3.6)所示.则问题(3.1)在mh情形下的最小二乘解X∗可表示为

其中任意.

例5令

则由引理5知故最小二乘解X∗∈R3×2,再由定理5有

则可得该方程的最小二乘解为

3.4 一般情形mh,pl

mh,pl情形下问题(3.1)的维数相容条件如下.

引理6若问题(3.1)有最小二乘解X ∈Rp×q,则需满足

i)为正整数其中α和β1分别为n与k和a与l的公约数;

证由半张量积的定义,

从上可知必为整数,并且有因此此外,若β=1,则l=p,显然与条件相悖,并且

因此证毕.

假定(3.1)满足引理6中的维数相容条件.记此时,转化为m=h,pl的形式,重复3.2小节的过程,则有下面结果.

定理6给定矩阵A∈Rm×n,B ∈Rh×k,C∈Ra×b和D∈Rl×d,A 和B 的奇异值分解如(3.6)所示.则问题(3.1)在mh,pl情形下的最小二乘解X∗可表示为

其中任意.

4 结论

半张量积作为一种新的研究工具在多线性函数、电力系统、布尔网络、密码学及模糊控制等领域有广泛地应用.本文将半张量积应用于矩阵方程求解问题,研究了半张量积下矩阵方程组AX=B,XC=D的最小二乘解,分矩阵-向量方程(X∈Rp)和矩阵-矩阵方程(X∈Rp×q)两种情形展开讨论.结合半张量积的定义给出问题有解的相容条件,即系数矩阵维数需满足的关系式,进而将半张量积下的问题转化为普通矩阵乘积下的矩阵方程最小二乘问题,结合广义逆,矩阵微分及奇异值分解给出问题解的具体解析表达式.对每一种情形给出简单的数值算例验证理论结果的正确性.

参考文献

[1]Horn R A,Johnson C R.Topics in matrix analysis[M].New York:Cambridge Univ.Press,1991.

[2]程代展,齐洪胜.矩阵的半张量积:理论与应用[M].北京:科学出版社,2011.

[3]Cheng D Z,Zhao Y.Semi-tensor product of matrices-a convenient new tool[J].Chin.Sci.Bull.,2011,56:2664–2674.

[4]马进,程代展,梅生伟,卢强.基于半张量理论的电力系统稳定域边界逼近(二)应用[J].电力系统自动化,2006,11:7–12.

[5]Feng J E,Yao J,Cui P.Singular Boolean network:semi-tensor product approach[J].Sci.China Ser.F:Inform.Sci.,2013,56:1–14.

[6]高博.基于半张量积的几类密码算法的研究[D].北京:北京交通大学,2014.

[7]Xu M R,Wang Y Z.Robust graph coloring based on the matrix semi-tensor product with application to examination time tabling[J].J.Contr.The.Appl.,2014,2:187–197.

[8]Cheng D Z,Qi H S.Matrix expression of logic and fuzzy control[R].Seville:44th IEEE Conf.Dec.Control/Euro.Control Conf.(CCD-ECC),2005.

[9]Cheng D Z,He F,Xu T.On networked non-cooperative games:a semi-tensor product approach[R].Istanbul:Proc.9th Asian Control Conf.,2013.

[10]Yao J,Feng J E,Meng M.On solutions of the matrix equation AX=B with respect to semi-tensor product[J].J.Frank.Inst.,2016,353:1109–1131.

[11]Mitra S K.The matrix equations AX=C,XB=D[J].Linear Alg.Appl.,1984,59:171–181.

[12]Li F L,Hu X Y,Zhang L.Least-squares mirrorsymmetric solution for matrix equations(AX=B,XC=D)[J].Numer.Math.J.Chin.Univ.Engl.Ser.,2006,15:217–226.

[13]Li F L,Hu X Y,Zhang L.The generalized re flexive solution for a class of matrix equations(AX=B,XC=D)[J].Acta Math.Sci.Ser.B.Engl.Ed.,2008,28:185–193.

[14]Li F L,Hu X Y,Zhang L.The generalized anti-re flexive solutions for a class of matrix equations(BX=C,XD=E)[J].Comp.Appl.Math.,2008,27:31–46.

[15]Qiu Y Y,Wang A D.Least squares solutions to the equations AX=B,XC=D with some constraints[J].Appl.Math.Comp.,2008,204:872–880.

[16]Yuan Y X.Least-squares solutions to the matrix equations AX=B and XC=D[J].Appl.Math.Comp.,2010,216:3120–3125.