deepseek/deepseek-chat-v3.1

Exercise 7: No more vectors

We now investigate the Vector Annihilation Problem (VAP):
Input: Matrices M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, vector v∈Z3v\in\mathbb{Z}^3
Output: Do there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that A1A2⋯Alv=0A_1A_2\cdots A_lv=0?

Our goal is to show that the VAP is undecidable.

Subproblem a (5.0/5.0P) 

Let M:=(0v−v)M:=\begin{pmatrix}0 & v & -v\end{pmatrix}, with v∈Z3v\in\mathbb{Z}^3, and M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, where M1,...,MkM_1,...,M_k are invertible. Show that the VAP for M,M1,...,Mk;vM,M_1,...,M_k;v has a solution if and only if there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that MA1A2⋯Alv=0MA_1A_2\cdots A_lv=0.

We show that the VAP for matrices M,M1,…,MkM, M_1, \ldots, M_k and vector vv has a solution if and only if there exists a sequence A1,…,Al∈{M1,…,Mk}A_1, \ldots, A_l \in \{M_1, \ldots, M_k\} such that MA1⋯Alv=0M A_1 \cdots A_l v = 0.

Let M=(0v−v)M = \begin{pmatrix} 0 & v & -v \end{pmatrix}, so for any vector w∈Z3w \in \mathbb{Z}^3, Mw=(w2−w3)vM w = (w_2 - w_3) v.

Proof of equivalence:

- (⇒) Suppose there exists a sequence B1,…,Bl∈{M,M1,…,Mk}B_1, \ldots, B_l \in \{M, M_1, \ldots, M_k\} such that B1B2⋯Blv=0B_1 B_2 \cdots B_l v = 0.
  - If v=0v = 0, then MIv=M0=0M I v = M 0 = 0, so the empty sequence (from {M1,…,Mk}\{M_1, \ldots, M_k\}) satisfies MIv=0M I v = 0.
  - Assume v≠0v \neq 0. Since M1,…,MkM_1, \ldots, M_k are invertible and MM is singular, the product B1⋯BlB_1 \cdots B_l must be singular, so it must include MM at least once.
  - Let jj be the largest index such that Bj=MB_j = M. Write the sequence as PMQP M Q, where QQ is a product of matrices from {M1,…,Mk}\{M_1, \ldots, M_k\} (possibly empty), and PP is a prefix (which may contain MM).
  - Then PMQv=0P M Q v = 0. Let u=Qvu = Q v, so PMu=0P M u = 0.
  - Since Mu=cvM u = c v for some scalar c=u2−u3c = u_2 - u_3, we have P(cv)=cPv=0P (c v) = c P v = 0.
  - Case 1: If c=0c = 0, then Mu=0M u = 0, so M(Qv)=0M (Q v) = 0. Since QQ is a sequence from {M1,…,Mk}\{M_1, \ldots, M_k\}, we have MQv=0M Q v = 0.
  - Case 2: If c≠0c \neq 0, then Pv=0P v = 0. The length of PP is less than ll (since MM and QQ are removed). By induction on the sequence length (base cases: if length 0, v=0v=0 handled; if length 1, only MM with Mv=0M v = 0, then empty sequence works), since Pv=0P v = 0 with shorter length, by induction hypothesis, there exists a sequence RR from {M1,…,Mk}\{M_1, \ldots, M_k\} such that MRv=0M R v = 0.
  - In both cases, there exists a sequence from {M1,…,Mk}\{M_1, \ldots, M_k\} such that MM times it applied to vv is 0.

- (⇐) Conversely, if there exists A1,…,Al∈{M1,…,Mk}A_1, \ldots, A_l \in \{M_1, \ldots, M_k\} such that MA1⋯Alv=0M A_1 \cdots A_l v = 0, then the sequence M,A1,…,AlM, A_1, \ldots, A_l applied to vv gives MA1⋯Alv=0M A_1 \cdots A_l v = 0, so VAP has a solution.

Therefore, the equivalence holds.

Subproblem b (–/5.0P) 

Now show that the VAP is undecidable by reducing the 0101-MPCP.

Note: 0101-MPCP is the Modified Post Correspondence Problem with alphabet {0,1}\{0,1\}. Modified means that the first card given in the input must always be the first card used in a solution.

To show that the Vector Annihilation Problem (VAP) is undecidable, we reduce from the 0101-MPCP (Modified Post Correspondence Problem with alphabet {0,1}\{0,1\} where the first card must be used first).

Given an instance of 0101-MPCP with cards 11 to nn, where each card ii has top string uiu_i and bottom string viv_i over {0,1}\{0,1\}, we construct an instance of VAP as follows:

- Define the vector v=(1,1,1)T∈Z3v = (1,1,1)^T \in \mathbb{Z}^3. This represents the initial state where both top and bottom strings are empty, with enc(empty)=1\text{enc}(\text{empty}) = 1 (where enc(w)=2len(w)+num(w)\text{enc}(w) = 2^{\text{len}(w)} + \text{num}(w) for a string ww, and num(w)\text{num}(w) is the integer value of ww interpreted in binary).

- For each card ii, define an invertible matrix Bi∈Z3×3B_i \in \mathbb{Z}^{3 \times 3} as:
  Bi=(100num(ui)2len(ui)0num(vi)02len(vi))
  B_i = \begin{pmatrix}
  1 & 0 & 0 \\
  \text{num}(u_i) & 2^{\text{len}(u_i)} & 0 \\
  \text{num}(v_i) & 0 & 2^{\text{len}(v_i)}
  \end{pmatrix}
  
  This matrix updates the vector such that for a current state (1,a,b)T(1, a, b)^T, Bi(1,a,b)T=(1,enc(ui)+2len(ui)a,enc(vi)+2len(vi)b)TB_i (1, a, b)^T = (1, \text{enc}(u_i) + 2^{\text{len}(u_i)} a, \text{enc}(v_i) + 2^{\text{len}(v_i)} b)^T, which corresponds to appending the strings uiu_i and viv_i to the top and bottom strings, respectively. Since 2len(ui)≠02^{\text{len}(u_i)} \neq 0 and 2len(vi)≠02^{\text{len}(v_i)} \neq 0, each BiB_i is invertible.

- Define M=(01−101−101−1)M = \begin{pmatrix} 0 & 1 & -1 \\ 0 & 1 & -1 \\ 0 & 1 & -1 \end{pmatrix}, which is equivalent to [0 v −v][0 \, v \, -v] for v=(1,1,1)Tv = (1,1,1)^T.

Now, from subproblem a, the VAP for matrices M,B1,…,BnM, B_1, \ldots, B_n and vector vv has a solution if and only if there exists a sequence SS of matrices from {B1,…,Bn}\{B_1, \ldots, B_n\} such that MSv=0M S v = 0.

MSv=0M S v = 0 if and only if the second and third components of SvS v are equal. Let Sv=(1,a,b)TS v = (1, a, b)^T. Then aa and bb are the encodings of the top and bottom strings after applying the card sequence corresponding to SS. Since enc(w)\text{enc}(w) is injective (each string has a unique encoding), a=ba = b if and only if the top and bottom strings are equal.

Moreover, because the 0101-MPCP requires the first card to be used first, any sequence that makes the strings equal must start with card 11. This is because the first card determines the first symbol of the strings, and for the strings to be equal, they must start with the same symbol, which is enforced by card 11. Thus, the sequence SS must correspond to a card sequence starting with card 11, meaning that SS must have B1B_1 as the rightmost matrix (so that it is applied first to vv).

Therefore, MSv=0M S v = 0 if and only if the 0101-MPCP instance has a solution.

Since 0101-MPCP is undecidable, VAP is undecidable.

google/gemini-2.5-pro

Exercise 7: No more vectors

We now investigate the Vector Annihilation Problem (VAP):
Input: Matrices M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, vector v∈Z3v\in\mathbb{Z}^3
Output: Do there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that A1A2⋯Alv=0A_1A_2\cdots A_lv=0?

Our goal is to show that the VAP is undecidable.

Subproblem a (–/5.0P) 

Let M:=(0v−v)M:=\begin{pmatrix}0 & v & -v\end{pmatrix}, with v∈Z3v\in\mathbb{Z}^3, and M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, where M1,...,MkM_1,...,M_k are invertible. Show that the VAP for M,M1,...,Mk;vM,M_1,...,M_k;v has a solution if and only if there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that MA1A2⋯Alv=0MA_1A_2\cdots A_lv=0.

We want to show the equivalence:
The Vector Annihilation Problem (VAP) for the set of matrices $\{M, M_1, ..., M_k\}$ and vector $v$ has a solution if and only if there exist $A_1, ..., A_l \in \{M_1, ..., M_k\}$ such that $M A_1 A_2 \cdots A_l v = 0$.

Let's analyze the matrix $M = \begin{pmatrix}0 & v & -v\end{pmatrix}$. The columns of $M$ are the vectors $0$, $v$, and $-v$. For any vector $x = (x_1, x_2, x_3)^T \in \mathbb{Z}^3$, the product $Mx$ is a linear combination of its columns:
$Mx = x_1 \cdot 0 + x_2 \cdot v + x_3 \cdot (-v) = (x_2 - x_3)v$.
This property is central to the proof.

If $v=0$, then $M$ is the zero matrix. The VAP has a solution (e.g., $Mv=0$) and for any $A_1 \in \{M_1, ..., M_k\}$, we have $MA_1v = 0 \cdot (A_1 \cdot 0) = 0$. Thus the equivalence holds trivially. We assume $v \neq 0$ for the rest of the proof.
With $v \neq 0$, the property implies that $Mx = 0 \iff x_2 = x_3$.

**($\Leftarrow$) direction:**
Assume there exist matrices $A_1, ..., A_l \in \{M_1, ..., M_k\}$ such that $M A_1 \cdots A_l v = 0$.
We need to show that the VAP for the set of matrices $\{M, M_1, ..., M_k\}$ has a solution. This requires finding a sequence of matrices $B_1, ..., B_p$ from this set such that $B_1 \cdots B_p v = 0$.
Let's construct such a sequence: let $p=l+1$, and define $B_1 := M$ and $B_{i+1} := A_i$ for $i=1, ..., l$.
Each $B_i$ is in the set $\{M, M_1, ..., M_k\}$. The product is:
$B_1 B_2 \cdots B_{l+1} v = M A_1 \cdots A_l v$.
By our assumption, this product is equal to $0$. Thus, we have found a solution to the VAP, which proves this direction.

**($\Rightarrow$) direction:**
Assume the VAP for $\{M, M_1, ..., M_k\}$ and $v$ has a solution. This means there exists a sequence of matrices $B_1, ..., B_p$ from $\{M, M_1, ..., M_k\}$ such that $B_1 \cdots B_p v = 0$.

Since all matrices $M_1, ..., M_k$ are invertible, any product of them is also invertible. An invertible matrix cannot map a non-zero vector $v$ to the zero vector. Therefore, the sequence $B_1, ..., B_p$ must contain at least one occurrence of the matrix $M$.

Let $B_j = M$ be the *first* occurrence of $M$ in the sequence. Then the matrices $B_1, ..., B_{j-1}$ must be from the set $\{M_1, ..., M_k\}$. Let $A_{pre} = B_1 \cdots B_{j-1}$. Since $A_{pre}$ is a product of invertible matrices, it is invertible.
The equation is $A_{pre} M B_{j+1} \cdots B_p v = 0$.
Multiplying by $A_{pre}^{-1}$ from the left, we get $M B_{j+1} \cdots B_p v = 0$.

Let $u := B_{j+1} \cdots B_p v$. The equation becomes $Mu = 0$. From our initial analysis of $M$, and since $v \neq 0$, this is equivalent to the condition that the second and third components of $u$ are equal, i.e., $u_2 = u_3$.

Now we need to show that this implies the existence of a vector $z$ of the form $A_1 \cdots A_l v$ such that $Mz=0$. This is equivalent to finding such a $z$ with $z_2=z_3$.

Let's proceed by induction on the number of $M$'s in the sequence generating $u$. Let $u = C_1 \cdots C_q v$ (with $C_i = B_{j+i}$) and $u_2=u_3$.

*   **Base Case:** The sequence $C_1, ..., C_q$ contains zero occurrences of $M$.
    In this case, all $C_i$ are from $\{M_1, ..., M_k\}$. Then $u$ is of the form $A_1 \cdots A_q v$. We can choose $z=u$. Since $u_2=u_3$, we have $Mz=Mu=0$. The condition is satisfied.

*   **Inductive Step:** Assume that for any vector $w$ generated by a sequence with fewer than $N>0$ occurrences of $M$ and satisfying $w_2=w_3$, the desired property holds (i.e., there exists a $z=A_1\cdots A_l v$ with $Mz=0$).
    Now, let $u$ be generated by a sequence $C_1, ..., C_q$ with $N$ occurrences of $M$, and let $u_2=u_3$. Let $C_r=M$ be the first occurrence of $M$ in this sequence. Then $C_1, ..., C_{r-1} \in \{M_1, ..., M_k\}$.
    We can write $u$ as:
    $u = (C_1 \cdots C_{r-1}) M (C_{r+1} \cdots C_q v)$.
    Let $z_{pre} = (C_1 \cdots C_{r-1})v$ and $u_{suf} = (C_{r+1} \cdots C_q v)$.
    Note that $z_{pre}$ is of the form $A_1 \cdots A_{r-1} v$.
    Using the property of $M$, we have $M u_{suf} = ((u_{suf})_2 - (u_{suf})_3)v$.
    Substituting this into the expression for $u$:
    $u = (C_1 \cdots C_{r-1}) \left( ((u_{suf})_2 - (u_{suf})_3)v \right) = ((u_{suf})_2 - (u_{suf})_3) (C_1 \cdots C_{r-1}v) = ((u_{suf})_2 - (u_{suf})_3) z_{pre}$.
    We know $u_2=u_3$. This implies:
    $((u_{suf})_2 - (u_{suf})_3) (z_{pre})_2 = ((u_{suf})_2 - (u_{suf})_3) (z_{pre})_3$.
    This can be rewritten as $((u_{suf})_2 - (u_{suf})_3) \cdot ((z_{pre})_2 - (z_{pre})_3) = 0$.
    This equation implies that at least one of the factors must be zero:
    1.  $(z_{pre})_2 - (z_{pre})_3 = 0$: This means $(z_{pre})_2 = (z_{pre})_3$. The vector $z_{pre}$ is of the form $A_1 \cdots A_{r-1} v$. So we can set $z=z_{pre}$ and we have found a vector of the required form such that $Mz=0$.
    2.  $(u_{suf})_2 - (u_{suf})_3 = 0$: This means $(u_{suf})_2 = (u_{suf})_3$. The vector $u_{suf}$ is generated by the sequence $C_{r+1}, ..., C_q$, which contains $N-1$ occurrences of $M$. By the induction hypothesis, the existence of such a vector $u_{suf}$ implies that there is a vector $z$ of the form $A_1 \cdots A_l v$ with $Mz=0$.

In both cases, we conclude that there must be a vector $z = A_1 \cdots A_l v$ with $A_i \in \{M_1, ..., M_k\}$ such that $Mz=0$. This completes the induction and proves the $(\Rightarrow)$ direction.

Subproblem b (–/5.0P) 

Now show that the VAP is undecidable by reducing the 0101-MPCP.

Note: 0101-MPCP is the Modified Post Correspondence Problem with alphabet {0,1}\{0,1\}. Modified means that the first card given in the input must always be the first card used in a solution.

<empty>

openai/gpt-5

Exercise 7: No more vectors

We now investigate the Vector Annihilation Problem (VAP):
Input: Matrices M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, vector v∈Z3v\in\mathbb{Z}^3
Output: Do there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that A1A2⋯Alv=0A_1A_2\cdots A_lv=0?

Our goal is to show that the VAP is undecidable.

Subproblem a (–/5.0P) 

Let M:=(0v−v)M:=\begin{pmatrix}0 & v & -v\end{pmatrix}, with v∈Z3v\in\mathbb{Z}^3, and M1,...,Mk∈Z3×3M_1,...,M_k\in\mathbb{Z}^{3\times 3}, where M1,...,MkM_1,...,M_k are invertible. Show that the VAP for M,M1,...,Mk;vM,M_1,...,M_k;v has a solution if and only if there exist A1,...,Al∈{M1,...,Mk}A_1,...,A_l\in\{M_1,...,M_k\} such that MA1A2⋯Alv=0MA_1A_2\cdots A_lv=0.

Let M=[0  v  −v]M=[0\ \ v\ \ -v], so for every x=(x1,x2,x3)⊤∈Z3x=(x_1,x_2,x_3)^\top\in\mathbb{Z}^3 we have
Mx=(x2−x3) vMx=(x_2-x_3)\,v.
In particular, im(M)=Z⋅v\mathrm{im}(M)=\mathbb{Z}\cdot v and Mx=0Mx=0 iff x2=x3x_2=x_3.

(⇒) Suppose there is a product B1⋯Btv=0B_1\cdots B_t v=0 with each Bi∈{M,M1,…,Mk}B_i\in\{M,M_1,\dots,M_k\}.
Take the rightmost occurrence of MM and write B1⋯Bt=P M QB_1\cdots B_t=P\,M\,Q, where QQ is a product of invertible matrices from {M1,…,Mk}\{M_1,\dots,M_k\} and hence invertible.
Let x:=Qvx:=Qv; then Mx=svMx=s v with s:=x2−x3∈Zs:=x_2-x_3\in\mathbb{Z}.
Thus 0=P(Mx)=s⋅(Pv)0=P(Mx)=s\cdot(Pv).
If s=0s=0, then MQv=0MQv=0 and we are done, taking A1⋯Aℓ=QA_1\cdots A_\ell=Q.
If s≠0s\neq 0, then (over Z\mathbb{Z}, which has no zero divisors) Pv=0Pv=0.
This gives a shorter annihilating product.
Repeating the argument finitely many times, we either find a suffix Q′Q' of invertible matrices with MQ′v=0MQ'v=0, or we end with a product of only invertible matrices annihilating vv, which is impossible when v≠0v\neq 0.
(If v=0v=0, both statements are trivially true.)
Hence there exist A1,…,Aℓ∈{M1,…,Mk}A_1,\dots,A_\ell\in\{M_1,\dots,M_k\} such that MA1⋯Aℓv=0MA_1\cdots A_\ell v=0.

(⇐) Conversely, if such A1,…,AℓA_1,\dots,A_\ell exist, then the product MA1⋯AℓM A_1\cdots A_\ell (whose factors lie in {M,M1,…,Mk}\{M,M_1,\dots,M_k\}) annihilates vv, so the VAP instance has a solution.

Therefore, the VAP for M,M1,…,Mk;vM,M_1,\dots,M_k;v has a solution iff there exist A1,…,Aℓ∈{M1,…,Mk}A_1,\dots,A_\ell\in\{M_1,\dots,M_k\} with MA1⋯Aℓv=0MA_1\cdots A_\ell v=0.

Subproblem b (–/5.0P) 

Now show that the VAP is undecidable by reducing the 0101-MPCP.

Note: 0101-MPCP is the Modified Post Correspondence Problem with alphabet {0,1}\{0,1\}. Modified means that the first card given in the input must always be the first card used in a solution.

Reduction from 01-MPCP.

Let the 01-MPCP instance be cards (u_i, w_i) over {0,1}, with card 1 fixed as the first card in any solution.

Encoding. Work in base B=3 but map symbols by τ(0)=1, τ(1)=2. For a word a_1...a_m∈{0,1}^*, define
enc(a_1...a_m) := ∑_{j=1}^m τ(a_j)·3^{m-j} ∈ ℕ.
Because no digit 0 appears, enc is injective and concatenation is realized by the affine update
U ↦ 3^{|p|}·U + enc(p).

Matrices. For each card i, with lengths m_i=|u_i| and n_i=|w_i|, and α_i=enc(u_i), β_i=enc(w_i), define the invertible matrix
T_i :=
[ [1,            0,           0],
  [α_i,      3^{m_i},         0],
  [β_i,          0,      3^{n_i}] ]
∈ ℤ^{3×3}.
Let s_0:=(1,0,0)^\top and set the VAP input vector
v := T_1 s_0 = (1, enc(u_1), enc(w_1))^\top.
Let M := [0 v -v] as in part (a), and consider the VAP instance with matrices {M, T_1, …, T_k} and vector v.

Correctness. By part (a), this VAP instance has a solution iff there exist i_2,…,i_t such that
M T_{i_2}\cdots T_{i_t} v = 0.
By construction and induction on t, for any sequence i_2,…,i_t we have
T_{i_2}\cdots T_{i_t} v = (1, enc(u_1 u_{i_2}\cdots u_{i_t}), enc(w_1 w_{i_2}\cdots w_{i_t}))^\top.
Since Mx=(x_2−x_3)·v, the equality M T_{i_2}\cdots T_{i_t} v=0 holds iff
enc(u_1 u_{i_2}\cdots u_{i_t}) = enc(w_1 w_{i_2}\cdots w_{i_t}),
which, by injectivity of enc, holds iff
u_1 u_{i_2}\cdots u_{i_t} = w_1 w_{i_2}\cdots w_{i_t}.
This is exactly the existence of a solution to the 01-MPCP with the first card fixed to be card 1 (the case t=1 allows the solution consisting only of the first card).

Thus we have a many-one reduction from 01-MPCP to VAP. Since 01-MPCP is undecidable, VAP is undecidable.