# Linear algebra in a language

Let $L$ be a language whose alphabet has $n$ letters. We have a dictionary listing $k$ equivalent pairs of words, i.e. $A_i \sim B_i$ for $1 \leq i \leq k$, where $A_i$ and $B_i$ are distinct words. We know that one can reduce any word from the language to a word of length at most $100$, by replacing similar words (from the listing of the dictionary).

Prove that $k \geq n$.

• Maybe I'm missing something obvious, but what does this have to do with linear algebra? – Jason DeVito Apr 3 '11 at 20:51
• Could you write your solution please ? – Mahan Apr 3 '11 at 20:55
• I deleted my answer, as being wrong, but I think the idea of supposing that $k < n$ and then constructing a word with length greater than 100 which can't be reduced using the dictionary could work. – alejopelaez Apr 3 '11 at 21:40
• I`ll think on your idea , but now I just want to know , how we can translate the problem into linear algebra form ! Thanks in advance for your comments . – Mahan Apr 3 '11 at 21:44
• From OP's comment to a deleted answer: "I think there isn't any short proof without linear algebra, and there exists a short one with that because it's the first exercise of a paper for introducing linear algebra. (That paper just has some problems and nothing more.)" – Yuval Filmus Apr 4 '11 at 1:47

Let $a_i,b_i$ be vectors in $\mathbb{Z}^n$ expressing the number of letters of each type in $A_i,B_i$. If $k < n$ then we can find some non-zero integer vector $v$ (with no common divisor) which is orthogonal to all $a_i - b_i$. That means that the inner product with $v$ is invariant under the substitutions $A_i \leftrightarrow B_i$.
Now compute the inner product of $v$ with the histograms of all words of length at most $100$, and choose some number $M$ not appearing in this set of inner products. Construct some word $w$ with histogram whose inner product with $v$ is $M$ (here we use the fact that $v$ has no common divisor). The word $w$ cannot be reduced to $100$ letters or less.
Note that we can always find such a $w$ which is a power of a single character. So the intuition behind the earlier answer was correct.