|
|
本文用较初等的概率方法对"阿赛"第五题进行解答. 原题大意:
记 $A_n$ 为形如 $\{0,1\}^{n\times n}$ 的矩阵, 试估计 $\max\det A_n$ 的上下界?
上界比较容易想. 给定 $A_{n}$, 则
$$
2^{n}\det A_n=\det \begin{pmatrix}1&\mathbf 1^T\\\mathbf 0&2A_n\end{pmatrix}=\det \begin{pmatrix}1&\mathbf 1^T\\-\mathbf 1&\tilde A_n\end{pmatrix}=:\det B_{n+1}.
$$
其中 $\tilde A_n$ 为 $\{\pm 1\}^{n\times n}$ 中的矩阵. 记实对称矩阵 $C_{n+1}=B_{n+1}^TB_{n+1}$, 则 $C_n$ 特征值非负, 从而
$$
\sqrt{|\det B_n|}=\det C_n=\prod_{1\leq i\leq n+1}\lambda_i\leq \left(\dfrac{\lambda_1+\cdots \lambda_{n+1}}{n+1}\right)^{n+1}=\left(\dfrac{\mathrm{trace}(C_n)}{n+1}\right)^{n+1}.
$$
而 $\mathrm{trace}(C_n)\leq (n+1)^2$, 从而
$$
\det A_n\leq \dfrac{(n+1)^{(n+1)/2}}{2^n}.
$$
取等当且仅当 $B_n$ 各列两两正交.
继而估计下界. 以下先估计 $\det B_{n}^2$ 的期望. 记 $B_n=(b_{i,j})_{n\times n}$, 则
$$
\mathbb E[\det B_n^2]=\sum_{u,v\in S_n}(-1)^{\tau(u)+\tau(v)}\mathbb E\left[\prod_{i=1}^na_{i,u(i)}a_{i,v(i)}\right].
$$
此处不妨将 $B_n$ 视作 $\{\pm 1\}^{n\times n}$ 上的随机矩阵, 因为任意形如 $\begin{pmatrix}1&\mathbf 1^T\\-\mathbf 1&\ast\end{pmatrix}$ 的矩阵可通过行列正负变换对应 $\{\pm 1\}^{n\times n}$ 上的 $2^{2n-1}$ 个矩阵, 且这 $2^{n-1}$ 个矩阵的行列式平方值相等. 注意到
$$
\mathbb E\left[\prod_{i=1}^na_{i,u(i)}a_{i,v(i)}\right]=\left\{\begin{align*}&0&&u\neq v,\\
&1&&u=v.\end{align*}\right.
$$
从而
$$
\mathbb E[\det B_n^2]=\sum_{u\in S_n}1=|S_n|=n!.
$$
因此 $\det A_{n}^2$ 的期望为 $4^{-n}(n+1)!$. 而 $\det A_n\neq 0$ 的概率为
$$
\dfrac{(2^n-1)(2^n-2^{n-1})\cdots(2^n-2^{n-1})}{2^{n\times n}}=\prod_{k=1}^n(1-2^{-k}).
$$
由于 $\max \det A_n=\sqrt{\max \det A_n^2}$, 故
$$
\max\det A_n\geq \sqrt{\dfrac{4^{-n}(n+1)!}{\prod_{k=1}^n(1-2^{-k})}}.
$$
当 $n\to\infty$, 根号内分母趋向常数
$$
C_0:=\exp\left(-\sum_{m\geq 1}\dfrac{1}{m(2^m-1)}\right).
$$
对于分子, 找一个向下的 Stirling 逼近
$$
\geq \sqrt{2\pi (n+1)}\cdot \left(\dfrac{n+1}{e}\right)^{n+1}\cdot e^{(12n+13)^{-1}}.
$$
从而存在常数 $C$ 使得
$$
\max \det A_n\geq C\cdot \dfrac{(n+1)^{(n+1.5)/2}}{2^n e^{[n+1-1/(12n+13)]/2}}\quad \sim C'\cdot \left(\dfrac{n}{4 e}\right)^{n/2}.
$$
记 $B_n:=\dfrac{(n+1)^{(n+1)/2}}{2^n}$, 遂有粗略的估计
$$
C'\cdot \dfrac{B_n}{e^{n/2}}\leq \max \det A_n\leq B_n.
$$
实际上, $B_n/9\leq \max \det A_n\leq B_n$, 因此以上估计的确挺粗略的(不过对应付"阿赛"而言绰绰有余了). |
|
