整数値行列のベクトルによる行の置換

質問

以前からちびちび考えていたのですが
原理的に不可能なような気もして、
ひょっとすると人生を無為に過ごしているかもしれないので
質問させてください。

整数値M×N次元行列{a[m,n]}に対して
整数値N次元ベクトル{b[n]}を
　c[m,n] = a[m,n]+b[n] (mod q)
と作用させたときc[m,n]がa[m,n]の
行の値の置換となっている
すなわち、m=1,2,..,Mがある置換Pによって
P(1),P(2),...,P(M)と置きかえられるとき
　c[m,n] = a[P(m),n]
となっている、行列aとベクトルbの組、そしてq
を求めたいのですが
こんな組み合わせってあるのでしょうか？
※置換の数はM!通りあるわけなので
　それぞれに対応した変換を与える
　ベクトル{b[m]}の組{{b[m]}}が
　全部存在していて欲しいと思います。
※もちろん
　a[m,n] と a[m',n]はすべての(m,m')の組に対して
　等しくないとします。
多分、a[m,n] と a[m',n] の値を上手い具合に
不等間隔に並べればいいかと思うのですが...？

あるいは類似の問題（できれば、答えが導かれているもの）
を教えていただければと思います。

MやNに制限は設けませんが、
できればある程度の大きさがあったほうがいいです
（逆に、無限大というのもこまりますが）

以上、不明な点は補足させて頂きますので、
要求をお願い致します。
（回答はできるだけ簡単に
　あらすじだけでも結構ですのでよろしくお願いします。）

回答No.2

stomachman · ベストアンサー

この話、ベクトルも行列も関係ないでしょう。
列<a[m]> (m=1,2,....M。∀n,m(n≠m→a[n]≠a[m])）の各要素に定数bを加えて作った列 <c[m]> (∀m(c[m]=(a[m]+b) mod q)） が列<a[m]>の置換になっているようにしたい。そしてb（0＜b＜q ）を変えるだけで全ての置換が網羅されるようにしたい。
という問題ですね。違います？

そういう<M, <a[m]> , q>があったとしましょう。
さて、M個の要素に関する置換全部の集合をPとするとき、M個の要素に関する互換の集合SはS⊂P。従って、ある互換sについて
<c[m]> = <a[s(m)]> = <(a[m]+b) mod q>
となるbが存在する。従って任意のmについて、
<c[s(m)]> =<a[s(s(m))]> = <a[m]>
つまり
<a[m]> =<(a[m]+2b) mod q>
でなくてはなりません。よって、
2b ≡ 0 (mod q)
ゆえに2b=q でなくちゃならんことになりますね。
このようなbは一つしかない。一方、互換はM (M-1)/2個ある。よってM>2の時には無理。

だから、この問題は「不可能」が答、かな？

お礼

stomachmanさん。回答ありがとうございます。

証明了解いたしました。もともとの問題は x の関数 f_j(x) (j=0,1,2,...,N) があって、
　exp[ i (f_j(x)+ g(x)) ] = exp[ i f_P(j)(x) ]　（ i は虚数単位）
となるようなg(x)があったら、便利だろうな、というところから、行列になってしまいました。そういう都合がいいことはそうそう起こらないと思っていましたがやっぱりそうですか。
（※oodaikoさんが等差数列のときを示してくださったように、
　　同じ列に同じ値が複数含まれる場合はN＞１で
　　行単位の置換の意味がちょっと違うのだなと思いました。
　　多分、の場合は同じ列に同じ値が複数含まれる場合を許す場合だと思います。
　　a[1,1]=1, a[1,2]=0, a[2,1]=1, a[2,1]=1 のようにです。
　　ただ、stomachmanさんの証明自体は生きますよね。）

方法としては、似たような置き換えを何回かくりかえしてもいいかと思っています。
（ごめんなさい、問題自体が固まっていないもんで。最終目標は、「とにかく足し算だけで置き換える」ということなんです。）
a[m,n]+b_w[n] (mod q_w) (w=1,...,W)
として（Wはできるだけ小さく）、何回か繰り返していつかは、目的とする置換になっているというようなイメージです。（歯車のついたくるくるお絵かき定規（？）みたいに（スピログラフというらしいです）。）
ともあれ、stomachmanさんのおかげで一歩前進です。ありがとうございます。