p***c
发帖数: 2403 | 1 给定一个方阵G＝(g(i,j)), 假设 对任意的一个置换p都有
sum_i g(i,i) \geq sum_i g(i, p(i))
求证不存在同阶方阵 X 满足
（1）X的第i行元素之和等于第i列元素之和
（2）所有元素非负
（3）sum_i sum_j x(i,j)g(i,i) < sum_i sum_j x(i,j)g(i,j)
2阶方阵这是显然的，对于3阶以上的，证了几个小时证不出来。我太笨了。 | f*****e
发帖数: 2992 | 2 g(i,i)+g(j,j)>=g(i,j)+g(j,i)
然后对1，2，3做推导。
【在 p***c 的大作中提到】
: 给定一个方阵G＝(g(i,j)), 假设 对任意的一个置换p都有
: sum_i g(i,i) \geq sum_i g(i, p(i))
: 求证不存在同阶方阵 X 满足
: （1）X的第i行元素之和等于第i列元素之和
: （2）所有元素非负
: （3）sum_i sum_j x(i,j)g(i,i) < sum_i sum_j x(i,j)g(i,j)
: 2阶方阵这是显然的，对于3阶以上的，证了几个小时证不出来。我太笨了。
| p***c
发帖数: 2403 | 3 我试过这样做
但是会出现 x(j,i)g(i,j) 这样子地项，没办法继续做下去啊
【在 f*****e 的大作中提到】
: g(i,i)+g(j,j)>=g(i,j)+g(j,i)
: 然后对1，2，3做推导。
| p***c
发帖数: 2403 | 4 N=3的情况下可以用暴力法证出来
不过我还没有看到怎么推广到一般的情形
【在 p***c 的大作中提到】
: 我试过这样做
: 但是会出现 x(j,i)g(i,j) 这样子地项，没办法继续做下去啊
| E*****T
发帖数: 1193 | 5 （3）sum_i sum_j x(i,j)g(i,i) < sum_i sum_j x(i,j)g(i,j)
sum_i sum_j x(i,j)g(j,j) < sum_i sum_j x(i,j)g(i,j)
一加应该就是你要证得。 | p***c
发帖数: 2403 | 6 谢谢，我太笨了，还是看不出来，能再解释解释吗
【在 E*****T 的大作中提到】
: （3）sum_i sum_j x(i,j)g(i,i) < sum_i sum_j x(i,j)g(i,j)
: sum_i sum_j x(i,j)g(j,j) < sum_i sum_j x(i,j)g(i,j)
: 一加应该就是你要证得。
| l*****e
发帖数: 65 | 7 I will try a prove using the matrices operations.
The G satisfies that Tr(G) >= Tr(GP) for any permutation matrix P.
Assume your X exists, then the conditions (1) and (2) means that there
exists a diagonal positive-entry matrix Y, such that X+Y is a multiple of a
doubly-stochastic matrix, namely all the column sums and the row sums are
the same. Use a classical result of Birkhoff-von Neumann, X+Y is a
combination of permutation matrices with positive coefficients.
Let D=D(G) be the diagonal matrix whose diagonal entry is equal to the
diagonal element of G correspondingly. D is also the diagonal of G^T.
Let J be the all 1 matrix, then Condition(3) is equivalent to
Tr(DXJ) < Tr (X G^T). Notice that Y is diagonal, then Tr(D Y J)= Tr(DY)= Tr(
Y G^T). Therefore, Tr( D(X+Y)J ) < Tr( (X+Y)G^T).
But this is impossible, as for any permutation matrix P,
Tr (DPJ)= Tr(DJ)=Tr(D)=Tr(G) >= Tr (G P^T) = Tr(P G^T), so their convex
combination keeps the direction of inequality Tr( D(X+Y)J ) >= Tr( (X+Y)G^T)
QED.
【在 p***c 的大作中提到】
: 给定一个方阵G＝(g(i,j)), 假设 对任意的一个置换p都有
: sum_i g(i,i) \geq sum_i g(i, p(i))
: 求证不存在同阶方阵 X 满足
: （1）X的第i行元素之和等于第i列元素之和
: （2）所有元素非负
: （3）sum_i sum_j x(i,j)g(i,i) < sum_i sum_j x(i,j)g(i,j)
: 2阶方阵这是显然的，对于3阶以上的，证了几个小时证不出来。我太笨了。
| E*****T
发帖数: 1193 | 8 LZ竟然给了我个包子，我又想了一下我写得不对。
你可以参考LS的，我是看不懂的，我晚上再想想，想不出来包子退回。 | p***c
发帖数: 2403 | 9 谢谢，就是我看不懂:(
I will try a prove using the matrices operations.
The G satisfies that Tr(G) >= Tr(GP) for any permutation matrix P.
Assume your X exists, then the conditions (1) and (2) means that there
exists a diagonal positive-entry matrix Y, such that X+Y is a multiple of a
doubly-stochastic matrix, namely all the column sums and the row sums are
the same. Use a classical result of Birkhoff-von Neumann, X+Y is a
combination of permutation matrices with positive coefficients.
Let D=D(G) be the diagonal matrix whose diagonal entry is equal to the
diagonal element of G correspondingly. D is also the diagonal of G^T.
Let J be the all 1 matrix, then Condition(3) is equivalent to
Tr(DXJ) < Tr (X G^T). Notice that Y is diagonal, then Tr(D Y J)= Tr(DY)= Tr(
Y G^T). Therefore, Tr( D(X+Y)J ) < Tr( (X+Y)G^T).
But this is impossible, as for any permutation matrix P,
Tr (DPJ)= Tr(DJ)=Tr(D)=Tr(G) >= Tr (G P^T) = Tr(P G^T), so their convex
combination keeps the direction of inequality Tr( D(X+Y)J ) >= Tr( (X+Y)G^T)
QED.
【在 l*****e 的大作中提到】
: I will try a prove using the matrices operations.
: The G satisfies that Tr(G) >= Tr(GP) for any permutation matrix P.
: Assume your X exists, then the conditions (1) and (2) means that there
: exists a diagonal positive-entry matrix Y, such that X+Y is a multiple of a
: doubly-stochastic matrix, namely all the column sums and the row sums are
: the same. Use a classical result of Birkhoff-von Neumann, X+Y is a
: combination of permutation matrices with positive coefficients.
: Let D=D(G) be the diagonal matrix whose diagonal entry is equal to the
: diagonal element of G correspondingly. D is also the diagonal of G^T.
: Let J be the all 1 matrix, then Condition(3) is equivalent to
| E*****T
发帖数: 1193 | 10 这个正确，学习了。
a
【在 l*****e 的大作中提到】
: I will try a prove using the matrices operations.
: The G satisfies that Tr(G) >= Tr(GP) for any permutation matrix P.
: Assume your X exists, then the conditions (1) and (2) means that there
: exists a diagonal positive-entry matrix Y, such that X+Y is a multiple of a
: doubly-stochastic matrix, namely all the column sums and the row sums are
: the same. Use a classical result of Birkhoff-von Neumann, X+Y is a
: combination of permutation matrices with positive coefficients.
: Let D=D(G) be the diagonal matrix whose diagonal entry is equal to the
: diagonal element of G correspondingly. D is also the diagonal of G^T.
: Let J be the all 1 matrix, then Condition(3) is equivalent to
| l*****e
发帖数: 65 | 11
a
昨天不能输中文，感觉很别扭。 今天卷土重来，求个年头通达。
你给的Ｇ矩阵， 满足 Tr(G)>= Tr(G P^T), 或者说，Tr(G) >= Tr(P G^T)， 对所有
的置换矩阵P, 其中 G^T 指G的转置矩阵。 这意味着， 如果让D为由G的对角线上元素
组成的对角阵，J为所有n^2位置上全为1的矩阵，那么
Tr( DPJ )= Tr(DJ) = Tr (D) = Tr(G) >= Tr(P G^T)。 进一步， 如果有c_1, ..., c
_k 正数， 那么对凸组合 c_1 P_1 + ...+ c_k P_k 有
Tr ( D(c_1 P_1+ ... + c_k P_k) J ) >= Tr ( (c_1 P_1+...+c_k P_k) G^T ).
接下来考虑你给的X矩阵。 由于X元素非负（条件2）且行和等于列和 （条件1）， 那
么加上一个适当的对角矩阵（元素恒正）， 可以使得 X+Y 每一行和，每一列和都相等
。 这样的矩阵早由Birkhoff 和冯。 诺依曼所完全刻画， 存在一些正数c_1, ..., c_
k以及一些置换矩阵P_1, ..., P_k 使得
X+Y= c_1 P_1+...+c_k P_k。
条件3 等价于 Tr(DXJ) < Tr (X G^T). 可是 Tr(DYJ)= Tr(DY)= Tr (Y G^T), 故
这个X满足 Tr（D (X+Y) J) < Tr ( (X+Y) G^T). 可是这与之前的分析结论是相矛盾的。
你可以把所有不等式用求和式子表达， 从而规避Tr 迹函数。
【在 p***c 的大作中提到】
: 谢谢，就是我看不懂:(
:
: I will try a prove using the matrices operations.
: The G satisfies that Tr(G) >= Tr(GP) for any permutation matrix P.
: Assume your X exists, then the conditions (1) and (2) means that there
: exists a diagonal positive-entry matrix Y, such that X+Y is a multiple of a
: doubly-stochastic matrix, namely all the column sums and the row sums are
: the same. Use a classical result of Birkhoff-von Neumann, X+Y is a
: combination of permutation matrices with positive coefficients.
: Let D=D(G) be the diagonal matrix whose diagonal entry is equal to the
| p***c
发帖数: 2403 | 12 大谢，包子送上，除了那个定理没听说过以外，其它基本能看懂了。我再消化消化
谢谢
c
【在 l*****e 的大作中提到】
:
: a
: 昨天不能输中文，感觉很别扭。 今天卷土重来，求个年头通达。
: 你给的Ｇ矩阵， 满足 Tr(G)>= Tr(G P^T), 或者说，Tr(G) >= Tr(P G^T)， 对所有
: 的置换矩阵P, 其中 G^T 指G的转置矩阵。 这意味着， 如果让D为由G的对角线上元素
: 组成的对角阵，J为所有n^2位置上全为1的矩阵，那么
: Tr( DPJ )= Tr(DJ) = Tr (D) = Tr(G) >= Tr(P G^T)。 进一步， 如果有c_1, ..., c
: _k 正数， 那么对凸组合 c_1 P_1 + ...+ c_k P_k 有
: Tr ( D(c_1 P_1+ ... + c_k P_k) J ) >= Tr ( (c_1 P_1+...+c_k P_k) G^T ).
: 接下来考虑你给的X矩阵。 由于X元素非负（条件2）且行和等于列和 （条件1）， 那
|
|
