Question

怎么证明平衡运输问题系数矩阵的各阶子式行列式只能取0、-1、1三个值?

Answer 1

这个其实很简单,你自己想一下就能想出来了.

每列2个非零元素,一个正1,一个负1.

现在一个子行列式,取了某些行,某些列.

如果某列只有一个非零元,那这列跟没取一样,因为按这列展开后,等于剩下的行列式乘以一个正1或者负1.只需证剩下的行列式在{0,1,-1}里.

所以,假设子行列式每列都有2个非零元.于是,每列的和都是0,这样的行列式=0,因为可以做这样一个变换：把除了最后一行的所有行一一加到最后一行,使得最后一行全0,这个变换不改变行列式的值,且最后的那个行列式=0.