線形代数の問題で・・・

質問

頂点Ｖiを出て頂点Ｖjに至る長さｋの歩道の総数は、行列Ａ^ｋの（i,j）成分に等しいことを、ｋに関する帰納法を用いて証明せよ。

という問題を出されました。しかし、いくら考えてもわかりません。どうか、教えてください。

回答No.2

kony0 · ベストアンサー

行列Aは正方行列で、その次元はnとします。（nに本質的な意味は無いです。別にnが加算無限でもよい・・・のかも？）
そして、A(i,j)=1 (if Vi→Vjのパスがある場合), 0 (else)
で定義されているんでしょう。
つまり、存在するすべての枝の長さは１であるかと思います。
ちなみに、枝が無向グラフなら、行列Aは対称行列です。

「頂点Ｖiを出て頂点Ｖjに至る長さｋの歩道の総数」は
Σ(l:l→jの枝がある)「頂点Ｖiを出て頂点Ｖlに至る長さｋ－１の歩道の総数」
=Σ(l=1,2,...,n)「頂点Ｖiを出て頂点Ｖlに至る長さｋ－１の歩道の総数」×A(l,j)

ということで、私的には解決。

回答No.1

seven_triton

頂点はいくつあって，どのように配置されているのですか？行列Aはサイズはいくつで，どのような行列なんですか？