(雑) 転置原理について考えたこと

転置原理の競プロでの使い方について考えたことを雑に並べた。普段なら Twitter に書いているような内容だが、長かったので。

転置原理

非常に雑に言うと、以下のような定理である。

$A$ を $m \times n$ 行列とする。「任意の $n$ 次元ベクトル $v$ を入力とし、 $A v$ を計算する」ことができるアルゴリズムがあるなら、同じ時間計算量で「任意の $m$ 次元ベクトル $u$ を入力とし、 $A ^ {\top} u$ を計算する」ことができるアルゴリズムがある。アルゴリズムを具体的に構成することも出来る。

ただし、アルゴリズム内で使える操作に制限があったり、同じ時間計算量と言っても $\mathrm{O}(n + m)$ くらいの違いはあったりする。丁寧な説明は https://qiita.com/ryuhe1/items/c18ddbb834eed724a42b この記事などを読むと良い。

競プロにおける使われ方

計算したい $m$ 次元ベクトル $r$ が、 $m \times n$ 行列 $A$ と $n$ 次元ベクトル $\hat{v}$ を用いて $r = A \hat{v}$ と表せるとする。このとき、 $u$ を入力として $A ^ {\top} u$ を計算するアルゴリズムが発見できれば、転置原理から $v$ を入力として $A v$ を計算するアルゴリズムが存在し、 $\hat{v}$ を入力すれば $A \hat{v} = r$ が計算できる。実は、 $A v$ の計算は難しいが $A ^ {\top} u$ の計算は簡単であるというような例がいくつも存在するので、この議論は有用である。

考えたこと

$n, A, \hat{v}$ をどのように取るかというのは一意ではないので、どう取ると良いのか？という疑問が生まれる。要件は $A ^ {\top} u$ が高速に計算できるようなアルゴリズムを思いつけることである。そこで、 $n = n ^ * , A = A ^ * , \hat{v} = \hat{v} ^ *$ がそのような要件を満たすと仮定する。すると、実は $n = 1, A = r, \hat{v} = 1$ もまた要件を満たすように思われる ( $r$ を $m \times 1$ 行列、 $1$ を $1$ 次元ベクトルと見做している)。 $(A ^ * ) ^ {\top} u$ が高速に計算できるのだから、 $r ^ {\top} u = (A ^ * \hat{v} ^ * ) ^ {\top} u = (\hat{v} ^ * ) ^ {\top} \left ( (A ^ * ) ^ {\top} u \right )$ も高速に計算できることになるからである。結局、競プロにおける転置原理の利用は以下のように言い換えても良さそうに思えてくる。

計算したいベクトルを $r$ とする。 $u$ を入力として $r ^ {\top} u$ を高速に計算できるなら、 $r$ は高速に計算できる。

では、この特殊化された転置原理だけがあれば良いかというと、それも違うかもしれない。まず、 $r ^ {\top} u$ を高速に計算する時、 $r$ を直接求めて内積を取ることはできない。 $r$ を求めること自体が目的だったからである。転置原理の適用条件の都合上、 $r ^ {\top}$ を掛ける操作は何らかの線形変換の繰り返しによるものとなる。すると $A _ 1 A _ 2 \cdots A _ k u$ と計算しているのだが、計算結果がスカラーになるから $A _ 1$ は行ベクトルである。 $A _ 1 = (\hat{v} ^ * ) ^ {\top}, A _ 2 \cdots A _ k = (A ^ * ) ^ {\top}$ とおけば、これは $r = A ^ * \hat{v} ^ *$ と表示していることに他ならない。よって、結局は特殊化されていない転置原理に戻ってきてしまう。

多点評価とその転置を例にして試してみる。 $f(x) = \sum _ {i = 0} ^ {N - 1} c _ i x ^ i$ を $x = a _ 0, a _ 1, \dots, a _ {M - 1}$ で評価することを考える。これに特殊化された転置原理を適用してみると、以下のような問題を考えることになる。

$b _ 0, b _ 1, \dots, b _ {M - 1}$ に対し、 $\sum _ {j = 0} ^ {M - 1} b _ j f(a _ j)$ を求めよ。

この問題の (多点評価を直接使わない) 解法は以下のようになる。

各 $0 \leq i \lt N$ に対して $\sum _ {j = 0} ^ {M - 1} b _ j a _ j ^ i$ を計算する。これは $\sum _ {i = 0} ^ {N - 1} \sum _ {j = 0} ^ {M - 1} b _ j a _ j ^ i y ^ i = \sum _ {j = 0} ^ {M - 1} \frac{b _ j}{1 - a _j y}$ であるから、分数式の和の計算をして各係数を見ればよい。最後に、それらに $c _ i$ を掛けて足し合わせると答えを得る。

正直、これを思いつくのは難しい気がする。一方で、これは多点評価を $A _ {j , i} = a _ j ^ i , \hat{v} _ i = c _ i$ と定義される行列とベクトルの積で表現して、特殊化されていない転置原理を適用していると理解できる。私が個人的に解いてきた転置原理を利用する問題は、多くはこのパターンだったと思う。つまり、

$r$ を求めたい答えとして、 $r ^ {\top} u$ を計算しようとすると、結局 $r = A \hat{v}$ という表現を経由することになる。そのような $A, \hat{v}$ は様々なものが考えられるが、明らかに自然な表現が $1$ つあり、それが $r ^ {\top} u$ の計算にも役立つ。