Why are n-1 linearly independent equations sufficient to solve for the secret string in Simon's algorithm?

Question

Professor Vazirani mentions in this lecture on Simon's algorithm that $n-1$ linearly independent equations are sufficient to solve for $s_1,s_2,...,s_n$ from the following system:

$y_1^{(1)}s_1+...+y_{n}^{(n)}s_n=0$

$y_1^{(2)}s_1+...+y_{n}^{(2)}s_n=0$

$y_1^{(n-1)}s_1+...+y_{n}^{(n-1)}s_{n}=0$

I don't understand how that is possible. Don't we need $n$ linearly independent equations to solve for $n$ variables $s_1,...,s_n$ ?

P.S: PDF version of the lecture: http://www-inst.eecs.berkeley.edu/~cs191/sp12/notes/simon.pdf

Answer 1

There are $n$ equations. The first equation is that $\sum_i y_ia_i = 0$, which is given as equation (1) on page 2 of the linked PDF.

Answer 2

With only $n-1$ equations, the set of solutions is not a point but a one-dimensional subspace. But as all equations found a homogeneous ("$\ldots = 0$"), we cannot hope to encage the solution any better than up to linear factor. Fortunately, we work over $\Bbb F_2$, where a one-dimensional subspace consists of exactly one non-zero point and the zero vector.

Answer 3

A quote from https://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes8.pdf

Note that it is often said that you need n linearly independent vectors to solve for s. But this is incorrect, because we have $s\neq0^n$ and $s= 0^n$ is clearly always a solution to these equations. Thus we really are finding a two dimensional subspace which corresponds to this solution. Thus we need n−1 linearly independent vectors to find this subspace.

Another quote from https://www.cs.cmu.edu/~odonnell/quantum15/lecture06.pdf

each linearly independent $y_i$ cuts down the number of possibilities for s by half. So after n − 1 equations, there are $2^{n−1}/2^n = 2$ possibilities for s , one of whom is 0 which is ruled out assuming that s is non-trivial, hence s is given by the other possibility.