# Are these the basis vectors?

A basis of a vector space $$\V\$$ is a set of vectors $$\B\$$ such that every vector $$\\vec v \in V\$$ can be uniquely written as a linear combination of the vectors in $$\B\$$. In other words, let $$\B = \{\vec b_1, \dots, \vec b_n\}\$$ be a basis of some vector space $$\V\$$. For every possible $$\\vec v \in V\$$, we can say that

$$\vec v = \lambda_1 \vec b_1 + \lambda_2 \vec b_2 + \cdots + \lambda_n \vec b_n$$

for some unique real numbers $$\\lambda_1, \lambda_2, \dots, \lambda_n\$$. Note that this requires the vectors in $$\B\$$ to be linearly independent (i.e., you cannot write a vector in $$\B\$$ as a linear combination of other vectors in $$\B\$$).

For example, let $$\V = \mathbb R^2\$$ i.e. the set of all 2 dimensional vectors. We can see that $$\B = \left\{ \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix} \right\}\$$ is a basis of $$\V\$$, as any 2 dimensional vector $$\\vec v = \begin{pmatrix} x \\ y \end{pmatrix}\$$ can be written as

$$\vec v = \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}x + \begin{pmatrix} 0 \\ 1 \end{pmatrix}y$$

Furthermore, examine $$\B = \left\{ \begin{pmatrix} 1 \\ 1 \end{pmatrix}, \begin{pmatrix} -1 \\ 2 \end{pmatrix} \right\}\$$. As the two vectors are linearly independent, they must form a basis of $$\\mathbb R^2\$$, and so we can write any 2-dimensional vector as a combination of the two. For example,

$$\begin{pmatrix} 2 \\ -10 \end{pmatrix} = -2\begin{pmatrix} 1 \\ 1 \end{pmatrix} + -4\begin{pmatrix} -1 \\ 2 \end{pmatrix}$$

However, note that if we have $$\B = \left\{ \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix} \right\}\$$, then this does not form a basis for all 3 dimensional vectors. There exists no such $$\\lambda_1, \lambda_2\$$ such that

$$\begin{pmatrix} 4 \\ 6 \\ 10 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}\lambda_1 + \begin{pmatrix} 0 \\ 1 \\ 2 \end{pmatrix}\lambda_2$$

and so $$\B\$$ is not a basis for $$\\begin{pmatrix} 4 \\ 6 \\ 10 \end{pmatrix}\$$.

You are to take a vector $$\\vec v \in \mathbb Z^m\$$ of $$\m\$$ integers, and a list of $$\n\$$ vectors $$\B = \{\vec b_1, \dots, \vec b_n\}\$$. You should then output two distinct consistent values to indicate whether or not $$\B\$$ forms a basis for $$\\vec v\$$ (more precisely, whether $$\B\$$ forms a basis for some space containing $$\\vec v\$$). That is, whether or not there exists a unique set of numbers $$\\lambda_1, \lambda_2, \dots, \lambda_n\$$ such that

$$\vec v = \lambda_1 \vec b_1 + \lambda_2 \vec b_2 + \cdots + \lambda_n \vec b_n$$

You may assume that $$\\vec b_i \in \mathbb Z^m\$$ for all vectors $$\b_i \in B\$$ - that is, they all have the same number of elements as $$\\vec v\$$, and they are all integer vectors.

You may take the inputs in any reasonable, convenient format and method, including a list of lists of $$\B\$$, or a list of numbers for $$\\vec v\$$ etc. The output may be any two distinct, consistent values to indicate whether or not $$\B\$$ is a basis. You may freely choose these values.

This is , so the shortest code in bytes wins

## Test cases

B
v
Output (λ1, λ2, ..., λn or reason)

[[8, 1, 2], [-7, -8, -9], [-1, 9, -5]]
[12, 36, -4]
True (1, -1, 3)

[[-9, -3]]
[3, 1]
True (-1/3)

[[1, 0, 1], [0, 1, 2]]
[1, -1, -1]
True (1, -1)

[[1, 0, 1], [0, 1, 2]]
[4, 6, 10]
False (shown above)

[[7, -2], [-10, -6], [-4, 9]]
[1, -21]
False (too many unknowns, an infinite number of solutions exist)

[[-1, 8, 1, 6, 3], [8, -6, -5, -10, 6], [-8, -3, -3, -4, 5], [-6, -6, 0, 3, 9], [2, 2, 0, -1, -3]]
[1, 1, 1, 1, 1]
False ([-6, -6, 0, 3, 9] and [2, 2, 0, -1, -3] are linearly dependent, so any way of writing the sum is not unique)

• Note that "whether or not $B$ forms a basis for $\vec v$" isn't mathematially correct; vector spaces have bases but individual vectors do not (and replacing $\vec v$ by $\langle\vec v\rangle$ doesn't make it correct either). By the criteria described, we're being asked whether $B$ is linearly independent and simultaneously $\vec v \in{}$Span$B$. Dec 3, 2021 at 19:36
• @GregMartin Yeah, I'm not too happy with the wording, but I believe that, although it isn't technically correct, it makes enough sense in the context of the challenge. If you have a better way of expressing the concept that $\vec v can be expressed as some linear combination of a subset of$B\\$, feel free to edit. Dec 3, 2021 at 20:36
• made a stab at it. I agree that the challenge itself is described well enough Dec 3, 2021 at 21:03

# Octave, 4341 39 bytes

@(B,v)(r=rank(B))-rows(B)|r-rank([B;v])


Anonymous function that inputs the set of vectors as a matrix B with each vector in a row, and v as a row vector. The output is true (displayed as 1) if B is not a basis for v, and false (displayed as 0) if it is.

Try it online!

### How it works

The set of vectors defined by the rows of B is a basis for v if and only if the rank of the matrix B equals its number of rows (i.e. the rows of B are linearly independent) and the rank of the extended matrix with v as last row is the same (i.e. v is in the linear span of the rows of B).

To save bytes, the code checks if either of those conditions is not satisfied; that is, if the rank of B minus its number of rows is nonzero or if the rank of B minus that of the extended matrix is nonzero.

# JavaScript (ES6), 218 bytes

Expects (matrix)(vector). Returns $$\0\$$ or $$\1\$$.

m=>v=>!(g=m=>m.reduce(o=>m.some((r,y)=>r.some((_,x)=>m[y+w]&&(D=m=>+m||m.reduce((s,[v],i)=>v*D(m.map(([,...r])=>r).filter(_=>i--))-s,0))(m.slice(y,y-~w).map(r=>r.slice(x,x-~w)))/r[x+w]))*++w||o,w=0)-w)(m)&!~g([...m,v])


Try it online!

### How?

The method is the same as the one used by Luis.

To compute the rank of a matrix, we look for the largest sub-matrix of size $$\n\times n\$$ whose determinant is not equal to $$\0\$$. This is most probably not the shortest way of doing it.

# JavaScript (Node.js), 93 bytes

f=B=>1/B[p=B.find(t=>t),1]?!!p&&f(B.map(q=>q.map((v,i)=>v*p-q*p[i]).slice(1))):!p


Try it online!

For testcase [[8, 1, 2], [-7, -8, -9], [-1, 9, -5]], [12, 36, -4] it input as f([[8, -7, -1, 12], [1, -8, 9, 36], [2, -9, -5, -4]]). Extra 47 bytes may be needed if we have to input as matrix B and vector V as two parameters.

This function simply reduce the array using Gaussian elimination.

# Pari/GP, 46 bytes

f(a,b)=#a==matrank(a)&&#matintersect(a,Mat(b))


Try it online!

Takes a matrix and a column vector as input.

# R, 61 bytes

Or R>=4.1, 54 bytes by replacing the word function with \.

function(B,v,+=Matrix::rankMatrix)+B-nrow(B)|+rbind(B,v)-+B


Try it online!

# Wolfram Mathematica, 51 41 bytes

Tr[1^#]&@@Solve[i=0;s@++i&/@#.#==#2]===i&


-10 (!) bytes due to @att

Try it online!

• 41 bytes
– att
Dec 3, 2021 at 21:15

# Charcoal, 43 bytes

⊞θηＷ∧θ⌈Φ§θ⁰κ≔ＥΦθλＥκ⁻×μι×§§θ⁰ν§κ⌕§θ⁰ιθ⁼θ⟦Ｅη⁰


Try it online! Link is to verbose version of code. Explanation: Port of @tsh's JavaScript answer.

⊞θη


Append the vector to the basis.

Ｗ∧θ⌈Φ§θ⁰κ


Repeat until the basis becomes degenerate...

≔ＥΦθλＥκ⁻×μι×§§θ⁰ν§κ⌕§θ⁰ιθ


... perform Gaussian elimination on the basis, dropping the first row.

⁼θ⟦Ｅη⁰


Check whether the result is a zero vector.