假设对于一个图的邻接矩阵A n*n，存在一个n*n的0-1矩阵P，使
P^tAP=[B C] P^t是P的转置
[O D] <--BCOD是一个同一个矩阵
成立，
其中B是r*r,C(r,n-r),O是（n-r,r）的零矩阵,D(n-r, n-r) 1<=r<=n-1
1.证明：对于A的k次方矩阵A^k，1<=k<=n，可以用同样的P，表示成上面那个等式类似的样子
2.并说明这样的邻接矩阵A对应的图G有什么特殊的性质。
======
这是试题，考试邻近，完全不会很着急，所以请指点一下我解这样的题需要看什么书？离散、图论还是线代？
1。
(1)
0-1矩阵P满足条件：每行每列只有一个元素是1，其余都是0。
P是置换矩阵。
PP^t=E。
(2)
P^tA^kP=[P^tAP]^k
用归纳法证明
[P^tAP]^k=
[Bk Ck]
[O Dk]
证明如下:
ⅰ。
k=1时显然成立。
ⅱ。
设
P^tA^kP=
[Bk Ck]
[O Dk]
==>
P^tA^(k+1)P=
=[P^tA^(k)P][P^tAP]=(用矩阵分块乘法计算)
[BkB1 BkC1+CkD1]
[O DkD1 ]
=
[B(k+1) C(k+1)]
[O D(k+1)]
所以当k+1时成立。
==>
所有k...全部
1。
(1)
0-1矩阵P满足条件：每行每列只有一个元素是1，其余都是0。
P是置换矩阵。
PP^t=E。
(2)
P^tA^kP=[P^tAP]^k
用归纳法证明
[P^tAP]^k=
[Bk Ck]
[O Dk]
证明如下:
ⅰ。
k=1时显然成立。
ⅱ。
设
P^tA^kP=
[Bk Ck]
[O Dk]
==>
P^tA^(k+1)P=
=[P^tA^(k)P][P^tAP]=(用矩阵分块乘法计算)
[BkB1 BkC1+CkD1]
[O DkD1 ]
=
[B(k+1) C(k+1)]
[O D(k+1)]
所以当k+1时成立。
==>
所有k>0
P^tA^kP=[P^tAP]^k=
[Bk Ck]
[O Dk]
2。
设P=(p(i,j)),其中p(u(s),s)=1。
A=(a(i,j))。
P^tAP=(f(i,j),通过矩阵计算得
f(i,j)=∑{1≤k,l≤n}p(k,i)p(l,j)a(k,l)
p(k,i)p(l,j)=1
p(k,i)=p(l,j)=1
k=u(i),l=u(j)。
==>
f(i,j)=a(u(i),u(j))
当r+1≤i≤n,1≤j≤r时,
a(u(i),u(j))=f(i,j)=0
==>
图G从顶点v(u(i))到v(u(j))无边,其中r+1≤i≤n,1≤j≤r。
另外需要看线代的书和离散中的图论的内容(相对简单),
其中线代是基础。
本题和
不矛盾,没什么关系。
另，将A^k中的元素记为a（i,j,k), 对于A的任意元素(i,j),存在整数k=k（i，j）≤n,使a（i,j,k)>0，请证明A不满足等式
用反证法很简单:
设P^tAP=
[B1 C1]
[O D1]
成立,则
P^tA^kP=[P^tAP]^k=
[Bk Ck]
[O Dk]
而P^tA^kP只是A^k的行和列的置换,其中的元素是相同的。
比如:a(u(r+1),u(1),k)=0,任意k>0,和有k使
a(u(r+1),u(1),k)>0矛盾。
--k(i,j)是指一个≤n的整数。
和另外一题无矛盾,主要是条件不一样。
。
收起
