\[
A^Tu=u
\]
\(A\) 可逆，所以 \(A^T\) 也可逆。

\[
u=(A^T)^{-1}u.
\]

\[
(A^T)^{-1}=(A^{-1})^T,
\]

\[
(A^{-1})^Tu=u.
\]

令

\[
A^{-1}=
\begin{bmatrix}
| & | & & |\\
v_1&v_2&\cdots&v_n\\
| & | & & |
\end{bmatrix},
\]

其中 \(v_j\) 是 \(A^{-1}\) 的第 \(j\) 個 column vector。

故\(\langle \vec{v_j}, \vec{u} \rangle = 1
\)

對所有 \(j=1,\dots,n\) 都成立。

所以 \(A^{-1}\) 的每一個 column vector 的 entries 之和都是 1。

假設相反，假設 \(A^{-1}\) 也是 stochastic matrix。

令

\[
B=A^{-1}\quad B\in M_{n\times n}
\]

\[
AB=I
\]

\(B\) 的 \(j\)-th column 為

\[
\begin{bmatrix}
b_{1j}\\
\vdots\\
b_{nj}
\end{bmatrix}
\]

\[
A=\begin{bmatrix}a_1&\cdots&a_n\end{bmatrix}
\]

\[
Ab_j=e_j
\]

其中 \(e_j\) 是 \(j\)-th std basis

\[
b_{1j}a_1+\cdots+b_{nj}a_n=e_j
\]

\(B\) 是 stochastic matrix

\[
b_{ij}\ge 0\quad \forall i,j\in\{1,\ldots,n\}
\]

且必有一個 entry 非 0

但 \(e_j\) 除了 \(j\)-th entry 是 1 其他都是 0

故當 \(b_{ij}>0\)，\(a_i\) 的 \(j\)-th entry 以外須為 0

\(A\) 是 stochastic matrix，\(a_i\) 的 entries 和為 1

\(a_i\) 只能是 \(e_j\)，所以 \(\forall j\in\{1,\ldots,n\}\)

\(A\) 的 columns 是 \(e_1,\ldots,e_n\) 的排列組合

\(A\) 升至任意次方仍是 \(e_1,\ldots,e_n\) 的排列組合

不會 entries 全為正 \(\rightarrow\leftarrow\)

確實在論證問題時，一開始往哪個方向著手頗具挑戰性。小題(1)知道 $A^{-1}$ 每個 column 的 entry 之和為 $1$，下個問題自然是 $A^{-1}$ 會不會是 stochastic matrix. 也就是每個 entry 皆不為負。很容易找到 stochastic matrix 的 inverse 依然為 stochastic matrix, 例如 identity matrix 以及 type one 的 elementary matrix 皆是。所以我們會進一步考慮 regular 的情況會不會。

關於參考解答的想法應該是想找到所有 inverse 仍為 stochastic 的 stochastic matrix，再去說這些都不是 regular。從邏輯的角度來說，這個想法當然比原題更深入，也因此可能比原題困難。也就是原題僅需考慮 regular 的情況，而參考解答的意圖需要考慮的是所有的 stochastic matrix，大家應可了解其中差異。在論證時若覺不可行，可嘗試轉換思路，專注於 regular stochastic matrix 的特性著手。希望同學能運用學習到的性質處理。要注意不要誤用 regular stochastic matrix 乘上 stochastic matrix 會是 regular 這個錯誤概念（能找到反例嗎?）。也可思考利用 regular stochastic matrix 的極限處理看看。

上述的參考解答，論述上有瑕疵，例如 $b_{ij}=0$ 時對應的 column $\mathbf{a}_i$ 怎麼辦。這個瑕疵發生應該也是同學常犯的錯誤：就是太快下結論到 $\forall\, j$。也就是一開始固定 $j$ 時沒有注意到 $i$ 會因 $j$ 而變動。注意到這一點，再細心處理，應可將此瑕疵解決。另外最後結論 $A$ 的 column 是 $\mathbf{e}_i$ 的排列組合這樣的說法成熟度不夠，能不能用專業一點的說法？（別忘了 elementary matrix），這樣才能更清楚解釋下一段話『A升至任意次方仍是 $\mathbf{e}_i$ 的排列組合』。若證明成功，我們就得到比習題更完美的結果：所有 inverse 仍為 stochastic matrix 的 stochastic matrix 就是一些 type 1 的 elementary matrix 的乘積。