xor基底ってなあに？

※本記事は自分の勉強も兼ねて書いています。間違いや疑問等があれば遠慮せずお伝え下さい。
読者は、学部で線形代数の授業をとったことがある人や、高校数学が十分に出来て数学のセンスが多少ある人を想定しています。（あてはまらない人は読むなという意味ではない）

線形代数ってなあに？

線形代数では数と演算が一般化されます。小学生のときに交換法則、結合法則、分配法則について習ったはずです。例えば交換法則は

x + y = y + x

こういうやつです。これは引き算では成り立ちません。線形代数ではこのような性質を見つめて、数とそれに対して定義される演算を考えて、そこからさらに発展させていきます。線形代数学は下で定義される線形空間について考える分野であるという認識で概ね間違いないはずです。

数学の諸記号

$\alpha \in F$　$\alpha$が集合$F$の要素である。
$\forall \alpha\in F,P$　集合$F$の要素である全ての$\alpha$について$P$が成り立つ。
$\exists \alpha\in F,P$　集合$F$の要素である$\alpha$について$P$が成り立つものが存在する。
$A$ s.t. $B$　s.t.はsuch thatの略号で$A$について$B$を補足する。
$A\longrightarrow B$　$A$が成り立つとき$B$も成り立つ。

体ってなあに？

集合$F$の要素$\alpha , \beta$に対して加法$\alpha+\beta\in F$と乗法$\alpha\cdot\beta=\alpha\beta\in F$を定義します。また、加法より先に乗法を計算することにします。
このとき以下を満たす$F$を体といいます。

1. $\forall \alpha,\beta,\gamma\in F, (\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)$
2. $\exists0\in F$ s.t. $\forall \alpha\in F,\alpha+0=\alpha$
3. $\forall \alpha\in F,\exists(-\alpha)\in F$ s.t. $\alpha+(-\alpha)=0$
4. $\forall \alpha,\beta\in F, \alpha+\beta=\beta+\alpha$
5. $\forall \alpha,\beta,\gamma\in F, (\alpha\beta)\gamma=\alpha(\beta\gamma)$
6. $\exists1\in F$ s.t. $\forall \alpha\in F,1\alpha=\alpha$
7. $\forall\alpha\ne0\in F,\exists{(\alpha)}^{-1}\in F$ s.t. $\alpha{(\alpha)}^{-1}=1$
8. $\forall \alpha,\beta\in F, \alpha\beta=\beta\alpha$
9. $\forall \alpha,\beta,\gamma\in F, \alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma$

上の式の日本語での説明

以下ではわかりやすさのため、$F$の要素を「数」と表現していますが、性質を満たすものであればどんなものでもかまいません。

1. 加法について結合法則が成り立つ
2. 足しても変わらないという性質を持つ0（零元、加法単位元）が存在する
3. 全ての数について足すと0になる数（マイナス元、加法の逆元）が存在する
4. 加法について交換法則が成り立つ
5. 乗法について結合法則が成り立つ
6. 掛けても変わらないという性質を持つ1（乗法単位元）が存在する
7. 0以外の全ての数について掛けると1になる数（乗法の逆元）が存在する
8. 乗法について交換法則が成り立つ
9. 分配法則が成り立つ

これらが成り立つとき$0$（加法単位元）と$1$（乗法単位元）は必ずひとつだけです[証明略]。

減法は加法の逆元を足し、除法は乗法の逆元を掛けると定義することで四則演算が定義されます。
適当な集合と演算を考えて、体の性質を満たすなら体です。有名なのは有理数や複素数です。ちなみに整数だと、乗法の逆元が整数の範囲に入らないので体になりません。
他にも、mod998244353は体です。体なので、割り算が定義できます。素数ではない場合、乗法の逆元が存在しないことがあり、体ではありません。

線形空間ってなあに？

$F$を体とする。集合$V$の要素$\textbf{x} , \textbf{y}$、$F$の要素$\alpha$に対して加法$\textbf{x}+\textbf{y}\in V$とスカラー倍$\alpha\textbf{x}\in V$を定義します。
このとき以下を満たす$V$を$F$上の線形空間（ベクトル空間）といいます。

1. $\forall\textbf{x},\textbf{y},\textbf{z}\in V,(\textbf{x}+\textbf{y})+\textbf{z}=\textbf{x}+(\textbf{y}+\textbf{z})$
2. $\forall\textbf{x},\textbf{y}\in V,\textbf{x}+\textbf{y}=\textbf{y}+\textbf{x}$
3. $\exists\textbf{0}\in V$ s.t. $\forall\textbf{x}\in V,\textbf{x}+\textbf{0}=\textbf{x}$
4. $\forall\textbf{x}\in V,\exists(-\textbf{x})\in V$ s.t. $\textbf{x}+(-\textbf{x})=\textbf{0}$
5. $\forall\textbf{x}\in V,\forall\alpha,\beta\in F,(\alpha\beta)\textbf{x}=\alpha(\beta\textbf{x})$
6. $\forall\textbf{x}\in V,\forall\alpha,\beta\in F,(\alpha+\beta)\textbf{x}=\alpha\textbf{x}+\beta\textbf{x}$
7. $\forall\textbf{x},\textbf{y}\in V,\forall\alpha\in F,\alpha(\textbf{x}+\textbf{y})=\alpha\textbf{x}+\alpha\textbf{y}$
8. $\forall\textbf{x}\in V,1\textbf{x}=\textbf{x}$

$\textbf{x}\textbf{y}$のような演算は定義されていないことに注意して下さい。

これらが成り立つとき、$\textbf{0}$（加法単位元）は必ずひとつだけです[証明略]。

お察しの通り、高校で習うベクトルはこの性質を満たします。

以降、体の要素をスカラーと呼び、線形空間の要素をベクトルと呼ぶことにします。ちなみにベクトルは太字で書くことが多いです。他にも行列は大文字で書く、みたいな慣習があります。

部分空間

線形空間$V$の空でない部分集合$W$が$V$における和とスカラー倍の演算によって線形空間になるとき、$W$を$V$の部分空間と呼びます。

基底ってなあに？

線形結合

体$F$上の線形空間$V$から$k$個のベクトル$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$と体$F$から$k$個のスカラー$\alpha_1,\alpha_2,\dots,\alpha_k$を選び作られるベクトル

\sum_{i=1}^{k} \alpha_i\textbf{x}_i=\alpha_1\textbf{x}_1+\alpha_2\textbf{x}_2+\cdots+\alpha_k\textbf{x}_k

を$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$の線形結合（1次結合）と呼びます。

また、$\alpha_1,\alpha_2,\dots,\alpha_k$を自由に動かしたときの$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$の線形結合全体の集合を

\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\rbrack=\left\lbrace\sum_{i=1}^{k} \alpha_i\textbf{x}_i\middle\vert\alpha_i\in F\right\rbrace

で表します。また、$\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\rbrack$を$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$が張る空間といいます。

任意の$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\in V$について$\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\rbrack$は部分空間になります[証明略]。

線形独立

\sum_{i=1}^{k} \alpha_i\textbf{x}_i=\textbf{0} \longrightarrow \alpha_i=0

のとき、$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$は線形独立（1次独立）であるといいます。
このとき、

\sum_{i=1}^{k} \alpha_i\textbf{x}_i=\sum_{i=1}^{k} \beta_i\textbf{x}_i \longrightarrow \alpha_i=\beta_i

であることが容易に証明できます。

基底

線形空間$V$において$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$が線形独立で、$V=\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\rbrack$であるとき、$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$は$V$の基底であるといいます。

このとき、$\textbf{x}\in V$について、$$\textbf{x}=\sum_{i=1}^{k} \alpha_i\textbf{x}_i$$と表すことが出来、またこの$\alpha_1,\alpha_2,\dots,\alpha_k\in F$は必ず一意に定まります。これを用いて、
$\textbf{x}$を$(\alpha_1,\alpha_2,\dots,\alpha_k)$と表すことで、高校で習ったベクトルと同様に扱うことが出来ます。

次元

線形空間$V$の基底は一意には定まりませんが、基底を構成するベクトルの個数は一定です。これを次元と呼び、$\dim V$と表します。

基底を構成するベクトルの個数が一定である証明（多分書かない）

TODO

2元有限体ってなあに？

集合$\lbrace0,1\rbrace$について加法をxor、乗法をandで定義すると体になります。これを2元有限体と呼び、$\mathbb{F}_2$と表記します。$GF(2)$と書くこともあります。

$\mathbb{F}_2$が体である証明

定義から

0+0=0 

0+1=1

1+0=1 

1+1=0

0\cdot0=0 

0\cdot1=0

1\cdot0=0 

1\cdot1=1

である。よって$x,y\in \mathbb{F}_2$について、

0+x=x+0=x

1+x=x+1=\bar{x}

0\cdot x=x\cdot0=x\cdot\bar{x}=0

1\cdot x=x\cdot1=x\cdot x=x

x+x=0 

x+\bar{x}=1

\overline{\bar{x}}=x

\bar{x}+y=x+\bar{y}=\overline{x+y}

但し、$\bar{0}=1, \bar{1}=0$である。
加法と乗法について交換法則が確認できる。
また、加法単位元が$0$、乗法単位元が$1$であることが確認できる。
$x$の加法の逆元は$x$であり、$1$の乗法の逆元は$1$である。

(x+0)+y=x+(0+y)=x+y

(x+1)+y=\bar{x}+y=x+\bar{y}=x+(1+y)

加法について結合法則が確認できる。

(x\cdot0)\cdot y=x\cdot(0\cdot y)=0

(x\cdot1)\cdot y=x\cdot(1\cdot y)=x\cdot y

乗法について結合法則が確認できる。

0\cdot(x+y)=0\cdot x+0\cdot y=0

1\cdot(x+y)=1\cdot x+1\cdot y=x+y

分配法則が確認できる。
以上より$\mathbb{F}_2$は体である。

次に$\mathbb{F}_2$上の線形空間を考えます。$x_i\in \mathbb{F}_2$を用いて、$\textbf{x}=(x_1,x_2,\dots,x_n)$と表されるベクトルについて考えます。このように表されるベクトルの集合を$\mathbb{F}_2^n$と表記します。
スカラー倍を
$$\alpha\textbf{x}=(\alpha x_1,\alpha x_2,\dots,\alpha x_n)$$
2つのベクトル$\textbf{x},\textbf{y}\in \mathbb{F}_2^n$の和を
$$\textbf{x}+\textbf{y}=(x_1+y_1,x_2+y_2,\dots,x_n+y_n)$$
と定義すると、$\mathbb{F}_2^n$は線形空間となります。

加法単位元$\textbf{0}=(0,0,\dots,0)$です。

$\mathbb{F}_2^n$が線形空間である証明

TODO

以降では$(0,1,0,1)$というベクトルを表したいとき、$0101$や$5$などと表記します。

2元有限体上の線形空間における基底ってなあに？

本題です。
$\mathbb{F}_2^3$の場合を考えてみましょう。
定義から
$\mathbb{F}_2^3=\lbrace000,001,010,011,100,101,110,111\rbrace$
です。
$001,010,100$は$\mathbb{F}_2^3$の基底です。
上で書いたように基底は一意には定まりません。
この場合$011,101,111$なども考えられます。

$\mathbb{F}_2^n$の次元は$n$となります。

$\mathbb{F}_2^n$の次元が$n$である証明

TODO

$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$が線形独立のとき、$\textbf{x}_1+\textbf{x}_2,\textbf{x}_2,\dots,\textbf{x}_k$もまた線形独立であり、また
$$\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k\rbrack=\operatorname{span} \lbrack\textbf{x}_1+\textbf{x}_2,\textbf{x}_2,\dots,\textbf{x}_k\rbrack$$
が成り立ちます。これは$\textbf{x}_1\in\operatorname{span} \lbrack\textbf{x}_1+\textbf{x}_2,\textbf{x}_2,\dots,\textbf{x}_k\rbrack$から明らかです[ほんとか?]。
つまり、$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_k$と$\textbf{x}_1+\textbf{x}_2,\textbf{x}_2,\dots,\textbf{x}_k$はどちらも同じ部分空間の基底といえます。

行列による表現

ここで、

\textbf{x}_i=(x_{i1},x_{i2},\dots,x_{in})

として、下のような行列を考えます。（このような行列表現はあまり一般的ではないと思います。このあたりからほとんど資料がない状態で書いています。）

\begin{pmatrix}
x_{11} & x_{12} & \cdots & x_{1n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{k1} & x_{k2} & \cdots & x_{kn}
\end{pmatrix}

基底の変換はこの行列の行基本変形に対応します。（通常よくやる基底から$F^k$のベクトルにして、線形写像を行列で表現するときのあれとは別です。）
行は横で列は縦です。
行列の行基本変形とは

• $i$行目と$j(\ne i)$行目を入れ換える。（基底に順番は関係ありません。）
• $i$行目に$j(\ne i)$行目を足す。

この2つの操作です。（あくまで$\mathbb{F}_2$上の行列の場合）
上の$\textbf{x}_1$を$\textbf{x}_1+\textbf{x}_2$にしたような基底の変換は次の変形に対応します。

\begin{pmatrix}
x_{11}+x_{21} & x_{12}+x_{22} & \cdots & x_{1n}+x_{2n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{k1} & x_{k2} & \cdots & x_{kn}
\end{pmatrix}

次に、任意の$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_l\in\mathbb{F}_2^n$（線形独立でなくてよい）について、同様に行列で表現します。

\begin{pmatrix}
x_{11} & x_{12} & \cdots & x_{1n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{l1} & x_{l2} & \cdots & x_{ln}
\end{pmatrix}

これに行基本変形を繰り返し、$\textbf{x}_i=\textbf{0}$となる行数がなるべく多くなるようにしたときの$\textbf{x}_i\ne\textbf{0}$の行数が$\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_l\rbrack$の次元となります[要証明]。

問題を解くときに使える知識を得よう

基底の求め方

$\textbf{x}=(x_1,x_2,\dots,x_n)$の中で最も左（ベクトルを成分表示したときのインデックスが小さい方）に1があるものを$\operatorname{LSB}(\textbf{x})$と表現することにします。つまり下のようになります。

\operatorname{LSB}(\textbf{x})=C \longrightarrow x_j=0\quad1\le j <C,\quad x_C=1

$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_l\in\mathbb{F}_2^n$について、$\operatorname{span} \lbrack\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_l\rbrack$の基底を求めるのが目標です。
まず、$\operatorname{LSB}$が最小となるものと$\textbf{x}_1$を入れ換えることで、$\operatorname{LSB}(\textbf{x}_1)$が最小となるようにします。次に$\operatorname{LSB}(\textbf{x}_1)=\operatorname{LSB}(\textbf{x}_i)\quad2\le i\le l$となる$\textbf{x}_i$を$\textbf{x}_i+\textbf{x}_1$にします。この処理をすると、行列は下のような形になります。（$\operatorname{LSB}$が$1$になることもあります。）

\begin{pmatrix}
0 & \cdots & 1 & * & \cdots & * \\
0 & \cdots & 0 & * & \cdots & * \\
\vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
0 & \cdots & 0 & * & \cdots & *
\end{pmatrix}

次に$\textbf{x}_2$の$\operatorname{LSB}$が2番目に小さくなるよう同様にに変換します。$\textbf{x}_2$が$\textbf{x}_1$を除いて$\operatorname{LSB}$が最小になるように交換したあと、$\operatorname{LSB}(\textbf{x}_2)=\operatorname{LSB}(\textbf{x}_i)\quad3\le i\le l$となる$\textbf{x}_i$を$\textbf{x}_i+\textbf{x}_2$にします。

さらに、$\textbf{x}_{1\operatorname{LSB}(\textbf{x}_2)}=1$の場合、$\textbf{x}_1$を$\textbf{x}_1+\textbf{x}_2$にします。

これらの操作をあわせると、$\textbf{x}_{i\operatorname{LSB}(\textbf{x}_2)}=1$の場合、$\textbf{x}_i$を$\textbf{x}_i+\textbf{x}_2$にするといえます。

この操作を繰り返すと行列は下のような形になります。

\begin{pmatrix}
0     & \cdots & 1    & *     & 0    & *     & 0    & *     \\
0     & \cdots & 0    & 0     & 1    & *     & 0    & *     \\
\vdots& \ddots &\vdots&\vdots &\vdots&\vdots &\vdots&\vdots \\
0     & \cdots & 0    & 0     & 0    & 0     & 1    & *     \\
0     & \cdots & 0    & 0     & 0    & 0     & 0    & 0     
\end{pmatrix}

つまり

\begin{matrix}
\textbf{x}_i\ne\textbf{0}\quad(1\le i\le m\le l)\land\textbf{x}_i=\textbf{0}\quad(m\lt i\le l)\\
\operatorname{LSB}(\textbf{x}_i)\ne\operatorname{LSB}(\textbf{x}_j)\land\textbf{x}_{i\operatorname{LSB}(\textbf{x}_j)}=0\quad(1\le i\le m,1\le j\le m.i\ne j)
\end{matrix}

となります。
このとき$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_m$は線形独立です[要証明]。
そのため、求めたかった基底は$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_m$であることがわかります。（変換したため、もとの$\textbf{x}_1,\textbf{x}_2,\dots,\textbf{x}_m$とは違うことに注意して下さい）

この処理を行った行列はもとの線形空間に対して、必ず一意に定まります[要証明]。
つまり、$\mathbb{F}_2^n$上の線形空間の部分空間とその基底を一対一対応させることができます。

実際に求めてみよう

$\operatorname{span} \lbrack 10011,00011,11110,01110\rbrack$の基底を求める

\begin{pmatrix}
 1  & 0  & 0  & 1  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
 1  & 1  & 1  & 1  & 0  \\
 0  & 1  & 1  & 1  & 0  \\
\end{pmatrix}

\begin{pmatrix}
 1  & 0  & 0  & 1  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
 0  & 1  & 1  & 0  & 1  \\
 0  & 1  & 1  & 1  & 0  \\
\end{pmatrix}

\begin{pmatrix}
 1  & 0  & 0  & 1  & 1  \\
 0  & 1  & 1  & 0  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
 0  & 1  & 1  & 1  & 0  \\
\end{pmatrix}

\begin{pmatrix}
 1  & 0  & 0  & 1  & 1  \\
 0  & 1  & 1  & 0  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
\end{pmatrix}

\begin{pmatrix}
 1  & 0  & 0  & 0  & 0  \\
 0  & 1  & 1  & 0  & 1  \\
 0  & 0  & 0  & 1  & 1  \\
 0  & 0  & 0  & 0  & 0  \\
\end{pmatrix}

よって基底は$10000,01101,00011$です。

Pythonのコード

l=[0b10011,0b00011,0b11110,0b01110]
def xor_base(l):
    base=[]
    for i in l:
        for j in range(len(base)):
            if i>i^base[j]:
                i^=base[j]
        for j in range(len(base)):
            if base[j]>base[j]^i:
                base[j]^=i
        if i>0:
            base.append(i)
    return base
print(list(map(bin,xor_base(l))))
# ['0b10000', '0b11', '0b1101']

プログラムは上の様になります。
base[j]の最上位ビットをbとします。つまり1<<b <= base[j] < 1<<(b+1)。このときiのb番目のビットが1であるかはi>i^base[j]で判別できます[要証明]。
参考（abc283_g）

もっと問題を解く

ABC-F Odd or Even again

【インタラクティブ】整数nと、n個の要素の配列aが与えられます。aの要素はすべて1以上n-1以下の奇数です。
どこかにn個の01からなる配列pが存在します。以下の質問を最大n回行うことで、pの要素をすべて決定してください。

質問：i回目の質問では、1≦j≦nを満たす互いに異なるa[i]個の数を選択してください。すべてのjに関するp[j]の和の偶奇が回答されます。

制約：1≦n≦1000

ABC313-D Odd or Evenの改題です。
これを解きます。
$$\operatorname{bitcount}(b_i)=a_i\quad b_i\in\mathbb{F}_2^n\quad (1\le i\lt N)$$
となるように$b_i$を線形独立に選べばよいです。

参考：ABC313 Dの逆行列解法とライブラリ化【解説・ライブラリ】

面倒なので、構築するコードだけ書きます。
$n=1000$だと多分間に合わないですが、C++でbitsetを使っていい感じにやれば間に合うと思います。

def query(n,a):
    base=[]
    rt=[]
    for i,j in enumerate(a[:-1]):
        t=0
        u=0
        for k in range(min(i,j-1)):
            t^=base[k]
            u^=1<<(n-k-1)
        for k in range(i,n):
            u^=1<<(n-k-1)
        if t&(1<<(n-i-1))>0:
            u^=1<<(n-i-1)
        m=0
        while u.bit_count()>j:
            if m!=n-i-1 and u&(1<<m)>0:
                u^=1<<m
            m+=1
        rt.append(u)
        t^=u
        for k in range(len(base)):
            if base[k]>base[k]^t:
                base[k]^=t
        base.append(t)
    cnt=1
    u=1
    for i in range(n-1):
        if base[i]&1!=u&1 and cnt+1==a[n-1]:
            continue
        u^=base[i]
        cnt+=1
        if cnt==a[n-1]:
            break
    rt.append(u)
    return rt

簡単にいうと、i番目を選ぶときはi番目のbitを線形独立になるようにして、その後ろでbit_countがa[i]になるように調整する感じです。最後だけ後ろがないので違うことをします。

想定解

以下のように構築されたn×n行列Mは正則行列となります。

aをソートしておきます。i行目(0≤i<n)は、もし i + 1 ≤ a[i] ならば、(i + 1 - a[i]) ≤ j ≤ i を満たすすべてのjについて、M[i][j] = 1。それ以外は0。
そうでないなら、0 ≤ j ≤ a[i] + 1 を満たすすべてのjについてM[i][j] = 1としたうえで、M[i][i+1]だけ0にする。