counting solutions of system of linear equations

124 Views Asked by At

Suppose we are looking for the solutions $(X_1,...,X_{10}) $ of the system $ \sum_{i=1}^{10} X_i=0$, $ \sum_{i=1}^{10} iX_i=0$ over the Galois field $GF(11)$ where none of the $X_i$ is $10$. Which would be the best way of counting the number of these vectors? Thanks in advance.

1

There are 1 best solutions below

0
On

(Edited to start at $1$ instead of $0$)

For $a, b \in GF(11)$, $1 \le k \le 10$, let $N(k,a,b)$ be the number of solutions of $\sum_{i=1}^k X_i \equiv a$, $\sum_{i=1}^k i X_i = b$, with $X_i \ne 10$. Use the recurrence $$ N(k,a,b) = \sum_{x = 0}^{9} N(k-1,a-x (\text{mod}\ 11), a-kx (\text{mod }\ 11)) $$ with initial conditions $$\eqalign{N(1,a,a) &= 1 \ \text{if}\ a \ne 10\cr N(1,a,b) &= 0 \ \text{otherwise}\cr}$$