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 的大作中提到】
: 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 的大作中提到】
: 你的结论应该是错的。
: 举个反例
: 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 的大作中提到】
: 我的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 的大作中提到】
: Sorry。没看到那个绝对值符号。你原先的结论是对的。但是证明是
: 非常类似的。
: 见附件。（其中L是奇异的，因为它的每一列都可以用其他列线性表达。）
|
z*******9
发帖数: 167 | 6 Another little mistake.
See attachment.
【在 N***m 的大作中提到】
: why does Eq(2) hold?
|
N***m
发帖数: 4460 | 7 证的不错
【在 z*******9 的大作中提到】
: 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 的大作中提到】
: 证的不错
|
N***m
发帖数: 4460 | 9 well said,hehe
【在 z*******9 的大作中提到】
: 还是有点错
: 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 的大作中提到】
: 还是有点错
: 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 的大作中提到】
: Thanks for your help!
: 有网友给了我一个证明，比较常规的二次型简单缩放：
: http://www.newsmth.net/bbscon.php?bid=749&id=94395
: 我整理了一下，贴在附件里——
|
p**o
发帖数: 3409 | 12 Thanks! You're right.
【在 N***m 的大作中提到】
: 这个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 的大作中提到】
: 还是有点错
: 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 的大作中提到】
: 第一个例子举的很好，看来我主贴中提到的x_0构造得有问题
: 不过你这个关于rank的结论不正确吧，比如
: A =
: 1 1 -1
: 1 1 0
: -1 0 1
: >> rank(A)
: ans =
: 3
: >> D=diag(sum(abs(A)))
|
