院試を解いてみた（東大院 情報理工 数理情報 修士 専門 H24）

\newcommand{\T}{\mathsf{T}}
\newcommand{\i}{\mathrm{i}}
\newcommand{\d}{\mathrm{d}}
\DeclareMathOperator{\tr}{\mathrm{tr}}

東京大学大学院 情報理工学系研究科 数理情報学専攻 修士課程
入学試験問題 専門科目 数理情報学(24年度)
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2012suuri-j.pdf

手始めに第1問だけ解いてみました。といってもいろいろ手を抜いています。
いただいたコメント・ストック・View数次第で、ミスを直したりもうちょっと真面目に詳しく書いたり他の問題も解いたりするかもしれません。

#(1)

$A$の$(i,j)$成分を$A_{ij}$とすると，

\begin{align}
&\frac{1}{2^n}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_n=\pm 1}
\sigma^\T A \sigma\\
&=
\frac{1}{2^n}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_{n-1}=\pm 1}
\sum_{\sigma_n=\pm 1}
\sum_{i=1}^n\sum_{j=1}^n
A_{ij} \sigma_i \sigma_j\\
&=
\frac{1}{2^n}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_{n-1}=\pm 1}
\sum_{\sigma_n=\pm 1}
\left(
\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}A_{ij} \sigma_i \sigma_j
+\sum_{i=1}^{n-1}A_{in} \sigma_i \sigma_n
+\sum_{j=1}^{n-1}A_{nj} \sigma_n \sigma_j
+A_{nn}\sigma_n^2\right)\\
&=
\frac{1}{2^{n-1}}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_{n-1}=\pm 1}
\left(\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}A_{ij} \sigma_i \sigma_j+A_{nn}\right)\\
&=
\frac{1}{2^{n-1}}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_{n-1}=\pm 1}
\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}A_{ij} \sigma_i \sigma_j+A_{nn}\\
&=\dots\\
&=A_{11}+\dots+A_{nn}\\
&=\tr(A).
\end{align}

#(2)
答えは3．(3)の特殊な場合なので詳解は省略．

#(3)
$A$のJordan標準形$P^{-1}AP=\Lambda$の対角成分を$\lambda_1,\dots,\lambda_n$とすると，

\begin{align}
&\frac{1}{2^n}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_n=\pm 1}
\frac{1}{2\pi\i}
\oint_{\partial D}
\sigma^\T (zI-A)^{-1} \sigma
\d z\\
&=
\frac{1}{2\pi\i}
\oint_{\partial D}
\left(\frac{1}{2^n}
\sum_{\sigma_1=\pm 1}
\sum_{\sigma_2=\pm 1}
\dots
\sum_{\sigma_n=\pm 1}
\sigma^\T (zI-A)^{-1}\sigma\right)
\d z\\
&=
\frac{1}{2\pi\i}
\oint_{\partial D}
\tr\left((zI-A)^{-1}\right)
\d z\\
&=
\frac{1}{2\pi\i}
\oint_{\partial D}
\tr\left((zI-\Lambda)^{-1}\right)
\d z\\
&=
\frac{1}{2\pi\i}
\oint_{\partial D}
\sum_{k=1}^n\frac{\d z}{z-\lambda_k}\\
&=
\sum_{k=1}^n
\frac{1}{2\pi\i}
\oint_{\partial D}
\frac{\d z}{z-\lambda_k}\\
&=
\sum_{k=1}^n
\left\{
\begin{array}{ll}
1 & (\lambda_k\in D)\\
0 & (\lambda_k\notin D)\\
\end{array}
\right.
\end{align}