p**o 发帖数: 3409 | 1 A是一个real symmetric matrix, 非负对角阵D是A的degree matrix
(i.e. D = diag[d_i], where d_i=\sum_j |a_{ij}| )
记 A' = D^{-1/2} A D^{-1/2},显然也是一个对称阵
请问如何证明A'的最大特征值是1 ?
PS1. 我已经构造出一个x_0使得 A'x_0 = x_0,也就是说1是A'的一个特征值,
但不知道怎么证明它是最大特征值……
PS2. 根据Rayleigh-Ritz定理,最大特征值等于 max_{x^T x=1} x^T A' x
也就是说我只需要证x^T A'x <= 1 for all unit vector x
有高人能提供一些思路么?
先谢过~~ |
z*******9 发帖数: 167 | 2 你的结论应该是错的。
举个反例
A =
1.0753 2.6961 -2.6924
2.6961 0.6375 -0.9651
-2.6924 -0.9651 7.1568
>> d = sum(A);Dh = diag(1./sqrt(d));eig(Dh*A*Dh)
ans =
3.5358
-1.2248
1.0000
不过如果A是非负矩阵,那么结论是对的。
你可以先证明:
L=D-A是半正定,且最小的特征值是0。(L is called Laplacian matrix)
半正定是因为 x'Lx = 0.5*\sum_{ij} A_{ij} (x_i-x_j)^2 >=0,
0是特征值是因为 Le=0, where e is column vector with all ones.
易知
D^{-1/2}LD^{-1/2}和L拥有相同的惯性系数,即都是半正定且最小特征值为0
而
D^{-1/2}LD^{-1/2} = I-D^{-1/2} A D^{-1/2},
所以D^{-1/2} A D^{-1/2}
【在 p**o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : A是一个real symmetric matrix, 非负对角阵D是A的degree matrix : (i.e. D = diag[d_i], where d_i=\sum_j |a_{ij}| ) : 记 A' = D^{-1/2} A D^{-1/2},显然也是一个对称阵 : 请问如何证明A'的最大特征值是1 ? : PS1. 我已经构造出一个x_0使得 A'x_0 = x_0,也就是说1是A'的一个特征值, : 但不知道怎么证明它是最大特征值…… : PS2. 根据Rayleigh-Ritz定理,最大特征值等于 max_{x^T x=1} x^T A' x : 也就是说我只需要证x^T A'x <= 1 for all unit vector x : 有高人能提供一些思路么? : 先谢过~~
|
p**o 发帖数: 3409 | 3 我的D矩阵取了绝对值的。关于你的"反例":
>> A=[1.0753, 2.6961, -2.6924;
2.6961, 0.6375, -0.9651;
-2.6924, -0.9651, 7.1568];
>> D=diag(sum(abs(A)))
D =
6.4638 0 0
0 4.2987 0
0 0 10.8143
>> Ap=D^(-1/2)*A*D^(-1/2)
Ap =
0.1664 0.5115 -0.3220
0.5115 0.1483 -0.1415
-0.3220 -0.1415 0.6618
>> [U,L]=eig(Ap)
U =
0.7240 0.4198 -0.5473
-0.6769 0.5853 -0.4463
0.1330 0.6936 0.7080
L =
-0.3710 0
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的结论应该是错的。 : 举个反例 : A = : 1.0753 2.6961 -2.6924 : 2.6961 0.6375 -0.9651 : -2.6924 -0.9651 7.1568 : >> d = sum(A);Dh = diag(1./sqrt(d));eig(Dh*A*Dh) : ans = : 3.5358 : -1.2248
|
z*******9 发帖数: 167 | 4 Sorry。没看到那个绝对值符号。你原先的结论是对的。但是证明是
非常类似的。
见附件。(其中L是奇异的,因为它的每一列都可以用其他列线性表达。)
【在 p**o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的D矩阵取了绝对值的。关于你的"反例": : >> A=[1.0753, 2.6961, -2.6924; : 2.6961, 0.6375, -0.9651; : -2.6924, -0.9651, 7.1568]; : >> D=diag(sum(abs(A))) : D = : 6.4638 0 0 : 0 4.2987 0 : 0 0 10.8143 : >> Ap=D^(-1/2)*A*D^(-1/2)
|
N***m 发帖数: 4460 | 5 why does Eq(2) hold?
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Sorry。没看到那个绝对值符号。你原先的结论是对的。但是证明是 : 非常类似的。 : 见附件。(其中L是奇异的,因为它的每一列都可以用其他列线性表达。)
|
z*******9 发帖数: 167 | 6 Another little mistake.
See attachment.
【在 N***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why does Eq(2) hold?
|
N***m 发帖数: 4460 | 7 证的不错
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Another little mistake. : See attachment.
|
z*******9 发帖数: 167 | 8 还是有点错
L=D-A不一定是奇异的。
当且仅当sign(A)的rank为1的时候,等号才成立, see attachment.
否则等号不成立。一个例子是:
A =
5.5389 -0.6245 2.8300
-0.6245 -0.1261 0.5906
2.8300 0.5906 2.9794
>> d = sum(abs(A));Dh = diag(1./sqrt(d));D = diag(d);[U,S]=eig(Dh*A*Dh)
U =
0.3456 -0.5269 0.7765
0.8444 0.5355 -0.0125
-0.4093 0.6600 0.6299
S =
-0.2653 0 0
0 0.3313 0
0 0 0.9214
>> rank(sign(A))
ans =
3
===========================
【在 N***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 证的不错
|
N***m 发帖数: 4460 | 9 well said,hehe
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是有点错 : L=D-A不一定是奇异的。 : 当且仅当sign(A)的rank为1的时候,等号才成立, see attachment. : 否则等号不成立。一个例子是: : A = : 5.5389 -0.6245 2.8300 : -0.6245 -0.1261 0.5906 : 2.8300 0.5906 2.9794 : >> d = sum(abs(A));Dh = diag(1./sqrt(d));D = diag(d);[U,S]=eig(Dh*A*Dh) : U =
|
p**o 发帖数: 3409 | 10 Thanks for your help!
有网友给了我一个证明,比较常规的二次型简单缩放:
http://www.newsmth.net/bbscon.php?bid=749&id=94395
我整理了一下,贴在附件里——
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是有点错 : L=D-A不一定是奇异的。 : 当且仅当sign(A)的rank为1的时候,等号才成立, see attachment. : 否则等号不成立。一个例子是: : A = : 5.5389 -0.6245 2.8300 : -0.6245 -0.1261 0.5906 : 2.8300 0.5906 2.9794 : >> d = sum(abs(A));Dh = diag(1./sqrt(d));D = diag(d);[U,S]=eig(Dh*A*Dh) : U =
|
N***m 发帖数: 4460 | 11 这个aij可能为负阿,第2布有问题,应该先取aij绝对值
【在 p**o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Thanks for your help! : 有网友给了我一个证明,比较常规的二次型简单缩放: : http://www.newsmth.net/bbscon.php?bid=749&id=94395 : 我整理了一下,贴在附件里——
|
p**o 发帖数: 3409 | 12 Thanks! You're right.
【在 N***m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个aij可能为负阿,第2布有问题,应该先取aij绝对值
|
p**o 发帖数: 3409 | 13 第一个例子举的很好,看来我主贴中提到的x_0构造得有问题
不过你这个关于rank的结论不正确吧,比如
A =
1 1 -1
1 1 0
-1 0 1
>> rank(A)
ans =
3
>> D=diag(sum(abs(A)))
D =
3 0 0
0 2 0
0 0 2
>> Ap=D^(-1/2)*A*D^(-1/2)
Ap =
0.3333 0.4082 -0.4082
0.4082 0.5000 0
-0.4082 0 0.5000
>> [U,S]=eig(Ap)
U =
0.7559 0.0000 -0.6547
-0.4629 0.7071 -0.5345
0.4629 0.7071 0.5345
S =
-0.1667 0 0
【在 z*******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 还是有点错 : L=D-A不一定是奇异的。 : 当且仅当sign(A)的rank为1的时候,等号才成立, see attachment. : 否则等号不成立。一个例子是: : A = : 5.5389 -0.6245 2.8300 : -0.6245 -0.1261 0.5906 : 2.8300 0.5906 2.9794 : >> d = sum(abs(A));Dh = diag(1./sqrt(d));D = diag(d);[U,S]=eig(Dh*A*Dh) : U =
|
z*******9 发帖数: 167 | 14 当a_ij = 0的时候,a_ij x_i xj = |a_ij| |x_i| |xj|
我列出的条件是充分而不必要。
关于那个定理的描述不够严格,应该把
条件rank( sign(A)) = 1 改为:
存在B使得:
B_{ij} = A_{ij}, when A_{ij} \neq 0,
且rank(sign(B)) = 1.
所以你如果找到一个反例,A全不为零,rank(A)>1,
Ap=D^(-1/2)*A*D^(-1/2)的最大特征值为1,那我的结论和
推导是错的。在我来看,那就见鬼了。
在你的例子里,只要
B =
1 1 -1
1 1 -1
-1 -1 1
rank(B)=1,且A和B的非零元素都相等,所以Ap的最大特征还是为1。
【在 p**o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一个例子举的很好,看来我主贴中提到的x_0构造得有问题 : 不过你这个关于rank的结论不正确吧,比如 : A = : 1 1 -1 : 1 1 0 : -1 0 1 : >> rank(A) : ans = : 3 : >> D=diag(sum(abs(A)))
|