15
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ 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\$. \$\endgroup\$ Dec 3, 2021 at 19:36
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 3, 2021 at 20:36
  • \$\begingroup\$ made a stab at it. I agree that the challenge itself is described well enough \$\endgroup\$ Dec 3, 2021 at 21:03

7 Answers 7

14
\$\begingroup\$

Octave, 43 41 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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

JavaScript (Node.js), 93 bytes

f=B=>1/B[0][p=B.find(t=>t[0]),1]?!!p&&f(B.map(q=>q.map((v,i)=>v*p[0]-q[0]*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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

Port of Luis Mendo's answer.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Mathematica, 51 41 bytes

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

-10 (!) bytes due to @att

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 41 bytes \$\endgroup\$
    – att
    Dec 3, 2021 at 21:15
1
\$\begingroup\$

Charcoal, 43 bytes

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

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

⊞θη

Append the vector to the basis.

W∧θ⌈Φ§θ⁰κ

Repeat until the basis becomes degenerate...

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

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

⁼θ⟦Eη⁰

Check whether the result is a zero vector.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.