Given a set of vectors all of the same positive finite dimension, output a falsey value if they are linearly dependent and a truthy value if they are linearly independent. A set of vectors v1, v2, ... is linearly dependent if for some scalars a1, a2, ... not all equal to 0, a1v1 + a2v2 + ... = 0. (0 is the zero vector.)

Note: Using an inbuilt function to find the rank of a matrix or test vectors for linear dependence is not allowed.

Note 2: All input will be formed from integers.

Test cases (input -> output):

[[0,1],[2,3]] -> True
[[1,2],[2,4]] -> False
[[2,6,8],[3,9,12]] -> False
[[1,2],[2,3],[3,4]] -> False
[[1,0,0],[0,1,0],[0,0,1]] -> True
[[0]] -> False
[] -> True
[[1,1],[0,1],[1,0]] -> False
[[1,2,3],[1,3,5],[0,0,0]] -> False
  • 1
    \$\begingroup\$ Can we take the set of vectors as a rectangular matrix? \$\endgroup\$
    – Alex A.
    Commented Apr 19, 2016 at 22:52
  • 2
    \$\begingroup\$ May we call a determinant built-in? \$\endgroup\$
    – xnor
    Commented Apr 19, 2016 at 23:10
  • 5
    \$\begingroup\$ May we try to invert the matrix with a built-in and see if that succeeds? May we call a built-in to find all the eigenvalues? \$\endgroup\$
    – xnor
    Commented Apr 19, 2016 at 23:11
  • 10
    \$\begingroup\$ @poi830 That seems really ad-hoc. To write a solution that uses linear-algebra functions, it seems like I'd have to guess what you'd allow or not. That strikes me as a mild case of Do X without Y. I understand you don't want cheap solutions with built-ins that just do the problem, but it's a hard line to draw. In particular, many matrix norms and decompositions can indirectly tell you if a set of vectors are independent, even though that's not their purpose. \$\endgroup\$
    – xnor
    Commented Apr 19, 2016 at 23:21
  • 1
    \$\begingroup\$ Edited, determinants and inversions of the matrix are now allowed, but may not be helpful because the matrix is not always square. \$\endgroup\$
    – poi830
    Commented Apr 19, 2016 at 23:25

13 Answers 13


Julia, 28 27 bytes


This is an anonymous function that accepts a 2-dimensional array with the vectors as columns and returns a boolean. To call it, assign it to a variable.

For any real, non-singular matrix X, the square matrix XTX is positive definite. Since a matrix is non-singular if and only if all of its column vectors are linearly independent and non-singular implies XTX is positive definite, we can declare the vectors to be linearly independent if the product is positive definite. A matrix is positive definite if and only if all of its eigenvalues are strictly positive, or equivalently when its smallest eigenvalue is strictly positive.

So for an input matrix X, we construct XTX and get the minimum eigenvalue using eigmin(X'X). To account for floating point error, we check this against the machine precision, eps, rather than 0, to declare positivity. Since we also want empty input to return true, we can simply add the condition X==[].

Saved 1 byte thanks to Dennis!


Matlab - 19 16 bytes


If the product of the matrix and its transpose is singular, then the rows of the matrix are linearly dependent. The determinant is non-negative, and since the entries are integral (thank you Alex A.), the determinant is integral and can be compared to .5.

It would have been nice to just do @(A)~det(A*A'), but unfortunately det can give almost-zero for singular matrices.

Try it on ideone

  • \$\begingroup\$ I didn't want to do arbitrary thresholding Using eps is actually arbitrary too :-) Maybe you want to use Ideone to provide an online demostration of your code for the test cases in the challenge (see for example my Octave answer). And welcome to PPCG! \$\endgroup\$
    – Luis Mendo
    Commented Apr 20, 2016 at 10:46
  • \$\begingroup\$ @LuisMendo I meant the difference was in det vs rcond. rcond gives very small values for singular matrices compared to det. Will try to add ideone! \$\endgroup\$
    – Anna
    Commented Apr 20, 2016 at 11:53
  • \$\begingroup\$ My point is: how can you be sure that you need to compare with eps and not with 10*eps for example? Anyway, that probably happens to other answers too \$\endgroup\$
    – Luis Mendo
    Commented Apr 20, 2016 at 11:54
  • 3
    \$\begingroup\$ @AlexA. The claim is true. The rows of M being dependent with coefficients given by vector v means there that v*M=0. This implies that v*M*(M^T)=0, so M*M^T is singular, since it maps some nonzero vector to zero. Conversely, if M*(M^T) is singular, then there exists a vector v so that v*M*(M^T)=0, in which case (v*M)*(v*M)^T=0. But, only the zero vector has norm zero, so v*M=0, which means the rows of M have a linear dependence. \$\endgroup\$
    – xnor
    Commented Apr 20, 2016 at 22:21
  • 1
    \$\begingroup\$ Since the input matrix is guaranteed to only contain integers, a nonzero determinant will be at least 1, so you can do @(A)det(A*A')>.5 or similar. \$\endgroup\$
    – Alex A.
    Commented Apr 21, 2016 at 2:44

R, 72 60 bytes


This is a function that accepts the vectors as columns in a matrix as well as the dimensions of the matrix and returns a logical. To call it, assign it to a variable. It requires the pracma package to be installed but it doesn't have to be imported.

The actual checking for linear independence is done by row reducing the matrix to echelon form and checking whether that's equal to an identity matrix of matching dimension. We just need a special case for when the input is empty.

Saved 12 bytes with help from Luis Mendo!


Mathematica - 29 bytes


Uses the property that the product of the eigenvalues of matrix A is equal to the determinant of A.


>>  False

Julia, 14 bytes


Based on @Anna's MATLAB answer and @AlexA.'s Julia answer. Expects a matrix whose columns are the input vectors and returns a Boolean.

det returns a float, so we cannot compare the result directly with 0. However, since the entries of M are integers, the lowest possible positive determinant is 1.


julia> f = M->det(M'M)>.5
(anonymous function)

julia> [f(M) for M in(
         [0 2;1 3],
         [1 2;2 4],
         [2 3;6 9;8 12],
         [1 2 3;2 3 4],
         [1 0 0;0 1 0;0 0 1],
         [1 0 1;1 1 0],
         [1 1 0;2 3 0;3 5 0]
9-element Array{Any,1}:

NARS2000 APL, 12 bytes


How it works

(≡≤-.×)⊢+.×⍉  Monadic function. Right argument: M

           ⍉  Transpose M.
       ⊢      Yield M.
        +.×   Perform matrix multiplication.
              For empty M, this yields a zero vector (for some reason).
(     )       Apply this matrix to the matrix product:
   -.×          Compute the determinant.
                This (mistakenly) yields 0 if M is empty.
 ≡              Yield the depth of M (1 is non-empty, 0 if empty).
  ≤             Compare.
                Since 0≤0, this corrects the error.

Octave, 32 27 bytes

Thanks to @Suever for removing 5 bytes!


The code defines an anonymous function. To call it assign it to a variable or use ans. The result is a non-empty array, which in Octave is truthy if all its entries are nonzero.

Try all test cases online.

This is based on the reduced row echelon form of a matrix. A non-empty matrix is full-rank iff each row of its reduced row echelon form contains at least one non-zero entry. This is checked by condition any(rref(x)', where ' can be used to transpose instead of .' because the entries are not complex. The empty matrix is dealt with separately by the condition ~numel(x) (which is the same as isempty(x) but shorter).

  • \$\begingroup\$ Couldn't you remove the all based on this definition of truthy and falsey? ideone.com/Zd5gQa \$\endgroup\$
    – Suever
    Commented Apr 20, 2016 at 3:42
  • \$\begingroup\$ @Suever Yes! Thank you! \$\endgroup\$
    – Luis Mendo
    Commented Apr 20, 2016 at 9:36

JavaScript (ES6), 162


Reduce the matrix and check if every row has at least 1 non zero element.

Less golfed

  P=r=> P=r=>r.findIndex(v=>v)), // First nonzero element position or -1
  // sort to have P in ascending order, but rows all 0 are at top
  M.map(_=> // repeat transformation for the number of rows
      p = P(r),
      p > q
       ? (k=M[i], q=p, r)
         // row transform
         // note: a 0s row generate a NaN row as p is -1
       : r.map((v,j) => v*k[q] - k[j]*r[p])
  // return false if there are rows all 0 or all NaN


console.log=(...x)=>O.textContent += x +'\n'

;[[[0,1],[2,3]] // True
,[[1,2],[2,4]] // False
,[[2,6,8],[3,9,12]] // False
,[[1,2],[2,3],[3,4]] // False
,[[1,0,0],[0,1,0],[0,0,1]] // True
,[[0]] // False
,[[0,0],[1,1]] // False
,[] // True
,[[1,1],[0,1],[1,0]] // False
,[[1,2,3],[1,3,5],[0,0,0]] // False
,[[1,2,3],[4,5,6]] // True
<pre id=O></pre>


MATL, 13 11 bytes


Thanks to Luis for golfing off two bytes.

Based on Anna's MATLAB answer.


t              duplicate input
 !             transpose
  Y*           matrix product, yields X^T * X
    2$0Zn      determinant
         Yo    round

Python 2 with NumPy - 85 112 103 102 bytes

import numpy
try:print reduce(lambda a,b:a*b,numpy.linalg.eigvals(x))

Hopefully can get a few off, FGITW.

  • 3
    \$\begingroup\$ What is the significance of the |0 in the final line? \$\endgroup\$
    – orlp
    Commented Apr 20, 2016 at 15:33

MATL, 33 bytes


This uses current release (16.1.0) of the language, which predates the challenge.

Input format is

[0 1; 2 3]


[[0 1];[2 3]]

Try it online!


This uses only integer opeations, so it is not subject to rounding errors (as long as the involved integers don't exceed 2^52).

It works by applying the definition. It suffices to test for integer scalars a1, a2, ... between −S−1 and S+1, where S is the sum of absolute values of all numbers in the input 2D array. In fact much lower values of S could be used, but this one requires few bytes to compute.

All "combinations" (Cartesian product) of values a1, a2, ... between −S−1 and S+1 are tested. The input vectors v1, v2, ... are independent iff only one of the linear combinations a1v1+a2v2+... gives a 0 result (namely that for coefficients a1, a2, ... = 0).

|ssQ    % sum of absolute values of input plus 1
t_w     % duplicate, negate, swap
2$:     % binary range: [-S-1 -S ... S+1]
GZy1)   % push input. Number of rows (i.e. number of vectors), N
Z^      % Cartesian power. Gives (2S+3)×N-column array
!2$1!   % Permute dimensions to get N×1×(2S+3) array
G       % Push input: N×M array
*       % Product, element-wise with broadcast: N×M×(2S+3) array
Xs      % sum along first dimension (compute each linear combination): 1×M×(2S+3)
!       % Transpose: M×1×(2S+3)
Xa~     % Any along first dimension, negate: 1×1×(2S+3). True for 0-vector results
s       % Sum (number of 0-vector results)
2<      % True if less than 2

J, 18 bytes

1<:[:-/ .*|:+/ .*]

This is a tacit verb that accepts a matrix with the vectors as columns and returns 0 or 1 depending on whether the vectors are linearly dependent or independent, respectively.

The approach is based on Anna's Matlab answer and Dennis' Julia answer. For a matrix X, the square matrix XTX is singular (i.e. has zero determinant) if the columns of X are linearly independent. Since all elements of X are guaranteed to be integers, the smallest possible nonzero determinant is 1. Thus we compare 1 ≤ det|XTX| to get the result.

Examples (note that |: > is just for shaping the input):

  f =: 1<:[:-/ .*|:+/ .*]
  f |: > 0 1; 2 3
  f |: > 1 2; 2 4
  f |: > 2 6 8; 3 9 12
  f |: > 1 2; 2 3; 3 4
  f |: > 1 0 0; 0 1 0; 0 0 1
  f 0
  f (0 0 $ 0)
  f |: > 1 1; 0 1; 1 0
  f |: > 1 2 3; 1 3 5; 0 0 0

Made possible with help from Dennis!

  • \$\begingroup\$ I wonder if finding the inverse of the matrix is allowed. If it is, 1:@%. ::0: for 10 bytes could be used. I think it isn't. \$\endgroup\$
    – miles
    Commented Apr 27, 2016 at 21:59

Jelly, 5 2 bytes


Try it online!

  • \$\begingroup\$ You don't need the æ×Z part. ÆḊ is implemented as sqrt(det(A × A')) for non-square matrices. I'm not sure if that would count as a LI built-in though... \$\endgroup\$
    – Dennis
    Commented Apr 25, 2016 at 14:22
  • \$\begingroup\$ Determinant is allowed. \$\endgroup\$
    – Leaky Nun
    Commented Apr 25, 2016 at 14:28

Your Answer

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

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