格子

前回詰まっていた帰着をいじっていると, 一次変換の話になって固有ベクトルの話が出てきて困ったという話. しかもC^nじゃなくって, (Z/qZ)^nで. そのせいで, n|q-1が必要. 何だそりゃ.
で, 問題はZ/qZの元を要素とするn次正方行列があったときに, その固有ベクトルをn本, nの多項式時間で見つけられるか. 複素数上じゃなくってZ/qZ上で, さらに行列が特殊な形をしているので, 固有多項式がn次だろうが固有値は具体的に出る. どっかにあるだろうから, 参考文献探して引くか.

固有値わかってんだから, Rx=λxから(R-λI)x=0を解けばいいんじゃないか. これは解ける.