代数

guanmo1

已知 $a_{i j} \cdot a_{j i}=1,1 \leq i, j \leq n$. 求证: $\sum_{j=1}^n\left(\sum_{i=1}^n a_{i j}\right)^{-1} \leq 1$.

Czhang271828

证明大致思路, 晚点想想实际意义 (可能和低秩逼进有关): 设 $A=(a_{ij})_{n\times n}$.

Step 1: 存在 $k$ 使得 $\sum_{i\neq k,1,j>i} (a_{ij}-\dfrac{a_{1,i-1}}{a_{1,j-1}})\geq0$. 实际上, 就是用贪心算法构造一个置换 $\sigma\in S_n$ 使得 $P_\sigma^T AP_\sigma=B$. 其中 $P_\sigma$ 右作用于 $A$ 对应 $A$ 所有行在 $\sigma$ 下的变换. 因此 $B=(b_{ij})_{n\times n}:=(a_{\sigma(i),\sigma(j)})_{n\times n}$.

Step 2: 据 Step 1 之构造, 则
$$
B=\begin{pmatrix}1\\b_{12}^{-1}\\\vdots \\b_{1n}^{-1}\end{pmatrix}\cdot \begin{pmatrix}1\\b_{12}\\\vdots \\b_{1n}\end{pmatrix}^T+\begin{pmatrix}0&0_{n-1}^T\\0_{n-1}&M\end{pmatrix}.
$$
从而
$$
\begin{pmatrix}\sum_{i=1}^n b_{1i}\\\sum_{i=1}^n b_{2i}\\\vdots\\\sum_{i=1}^n b_{ni}\end{pmatrix}=\begin{pmatrix}1\\b_{12}^{-1}\\\vdots \\b_{1n}^{-1}\end{pmatrix}\cdot \begin{pmatrix}1\\b_{12}\\\vdots \\b_{1n}\end{pmatrix}^T\cdot \begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}+\begin{pmatrix}0&0_{n-1}^T\\0_{n-1}&M\end{pmatrix}\cdot \begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}.
$$
其中 $M$​ 各项和为负, 从而
$$
\begin{pmatrix}\sum_{i=1}^n b_{1i}\\\sum_{i=1}^n b_{2i}\\\vdots\\\sum_{i=1}^n b_{ni}\end{pmatrix}=\left(\sum_{j=1}^n b_{1j}\right)\cdot \begin{pmatrix}1\\b_{12}^{-1}\\\vdots \\b_{1n}^{-1}\end{pmatrix}+\begin{pmatrix}0&0_{n-1}^T\\0_{n-1}&M\end{pmatrix}\cdot \begin{pmatrix}1\\1\\\vdots \\1\end{pmatrix}.
$$
因此
$$
\sum_{j=1}^n\left(\sum_{i=1}^n a_{ij}\right)^{-1}=\sum_{j=1}^n\left(\sum_{i=1}^n b_{ij}\right)^{-1}\leq \dfrac{\left(\sum_{j=1}^n b_{1j}\right)}{\left(\sum_{j=1}^n b_{1j}\right)}=1.
$$
取等当且仅当 $\mathrm{rank}(A)=1$.