Problem
Let $\mathcal{A}$ be a finite nonempty subset of a finite vector space $\mathcal{V}$ over a Galois field $GF(s)$ ($s$ a prime power) and let $t$ be a positive integer such that
(1) any $t$ vectors in $\mathcal{A}$ are linearly independent;
(2) for any $v \in \mathcal{V}$, there exists $a_1,\ldots,a_{t-1} \in GF(s)$ and $\alpha_1,\ldots,\alpha_{t-1} \in \mathcal{A}$ such that
$$
v = a_1 \alpha_1 + \cdots + a_{t-1}\alpha_{t-1}
$$
Then we call $\mathcal{A}$ a basis of $\mathcal{V}$ with parameter $t$.
Suppose $\mathcal{A}_1$ and $\mathcal{A}_2$ are two basis of $\mathcal{V}$ with parameter $t$, then does $|\mathcal{A}_1| = |\mathcal{A}_2|$ hold?
Background
I came across this problem when I was considering this concrete example. Let $\mathcal{V} = GF(3)^3$ and $t=3$, then we can take
$$
\mathcal{A}_1 = \{(1,0,0),(0,1,0),(0,0,1),(1,1,1)\}
$$
$$
\mathcal{A}_2 = \{(1,0,0),(1,1,0),(1,1,1),(1,2,1)\}
$$
And they satisfy the conditions and have the same number of elements. I don't know if we can have general results as stated above. Any hints will be appreciated. Thanks!!!
Updates & Observations
(1) We can create such a $\mathcal{A}$ using a stepwise procedure. First let $\mathcal{C} := \varnothing$ and $\mathcal{S} := \mathcal{V}$. Then at each step we take a nonzero vector $x \in \mathcal{S}$, and update
$$
\mathcal{C} \leftarrow \mathcal{C} \cup \{x\},
\quad
\mathcal{S} \leftarrow \mathcal{S} \backslash \{\mbox{any }t-1\mbox{ linear combinations between }x\mbox{ and elements in }\mathcal{C}\}
$$
and repeat the step until $\mathcal{S} = \varnothing$. Finally, the set $\mathcal{C}$ will be what we desire.
Best Answer
Counterexamples exist.
They are essentially based on the fact that the output of the algorithm outlined in the last paragraph of the question may be wasteful in covering all the vectors of $V$. Making "smart" choices may result in a smaller set $\mathcal{A}$ than what we would get by greedily picking the first vector not violating the update rule.
IMHO a most striking way of seeing this is to appeal to the properties of so called perfect codes. It is known (highly non-trivial) that there are darn few perfect codes with covering radius $>1$, but we have the binary Golay code. It is a $12$-dimensional subspace $C$ of $W=GF(2)^{23}$. Perfectness here manifests itself as follows. Given a vector $x\in W$ there is a single vector not differing from $x$ at all ($x$ itself), $\binom {23}1=23$ vectors differing from $x$ at a single component, $\binom {23}2=23\cdot 11$ vectors differing from $x$ at exactly two components, and $\binom {23}3=23\cdot 7\cdot 11$ vectors differing from $x$ at exactly three components. Observe that $$1+23+23\cdot11+23\cdot7\cdot11=1+23\cdot89=2^{11}.$$ A truly remarkable fact is that these balls of radius three (w.r.t. the Hamming metric) centered at the vectors $x\in C$ cover the entire space $W$ seamlessly without any overlap whatsoever! In other words, all the $2^{23}=2^{12}\cdot 2^{11}$ vectors of $W$ are within Hamming distance three from a unique vector in $C$.
Let $H$ be a parity check matrix of the binary perfect Golay code. Here is one such (unless I miscopied it) $$ H=\left( \begin{array}{ccccccccccccccccccccccc} 1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0&0&0&0&0&0\\ 0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0&0&0&0&0\\ 0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0&0&0&0\\ 0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0&0&0\\ 0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0&0\\ 0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0&0\\ 0&0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0&0\\ 0&0&0&0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0&0\\ 0&0&0&0&0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1&0\\ 0&0&0&0&0&0&0&0&0&0&1&1&1&1&1&0&0&1&0&0&1&0&1\\ \end{array}\right). $$ The subspace $C$ consists of those vectors in $GF(2)^{23}$ that are orthogonal to all the rows of $H$, i.e. share an even number of $1$s with all the rows of $H$.
On with the counterexample. Let $V=GF(2)^{11}$. Let $\mathcal{A}$ be the set of $23$ columns of $H$. The perfectness of $C$ implies that any vector in $V$ is a sum of at most three of those columns. The minimum distance of $C$ is seven, implying that every set of seven columns of $H$ is linearly independent. This is standard coding theory, ask if you want these steps detailed. In particular, every set of four columns of $H$ is linearly independent. Therefore $\mathcal{A}$ is a basis of $V$ with parameter $t=4$.
The above calculation with binomial coefficients implies that:
But, consider the following subset $S$ of $V$ $$ S=\{ 10000000000, 01000000000, 00100000000, 00010000000, 11110000000\}. $$ That is, the first four vectors from the natural basis and their sum. Clearly all subsets of at most $t=4$ elements of $S$ are linearly independent, so the set $S$ has the property (1) with parameter $t=4$. Therefore we can use it as an input to the algorithm of the last paragraph, and keep adding new vectors from $V$ to it without violating property (1) until the property (2) is also satisfied, and we have a basis with parameter $t=4$. The output will be another basis $\mathcal{A}'$.
But, the vector $v=01110000000$ can be written in two obvious ways as a sum of at most three vectors from $S$. Therefore it can be written in at least two different ways as a sum of at most $t-1=3$ vectors from $\mathcal{A}'$. As per the second bullet we can conclude that $|\mathcal{A}'|>23$.
I'm fairly sure that we can find smaller counterexamples where the idea of seeding the algorithm with a smart and with a less smart initial set $S$ leads to bases with different cardinalities. I used the Golay code to produce a counterexample simpy because I find it kinda neat.