Linear Independence

Question

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 v₁, v₂, ... is linearly dependent if for some scalars a₁, a₂, ... not all equal to 0, a₁v₁ + a₂v₂ + ... = 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

Answer 1

Matlab - 19 16 bytes

@(A)det(A*A')>.5

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

Answer 2

Julia, 28 27 bytes

X->X==[]||eigmin(X'X)>eps()

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 X^TX 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 X^TX 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 X^TX 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!

Answer 3

R, 72 60 bytes

function(x,m,n)!is.null(x)&&all(pracma::rref(x)==diag(,m,n))

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!

Answer 4

Julia, 14 bytes

M->det(M'M)>.5

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.

Verification

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],
         zeros((1,1)),
         zeros((0,0)),
         [1 0 1;1 1 0],
         [1 1 0;2 3 0;3 5 0]
       )]
9-element Array{Any,1}:
  true
 false
 false
 false
  true
 false
  true
 false
 false

Answer 5

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.

Answer 6

Octave, 32 27 bytes

Thanks to @Suever for removing 5 bytes!

@(x)~numel(x)|any(rref(x)')

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).

Answer 7

Mathematica - 29 bytes

#=={}||Det[#.Transpose@#]!=0&

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

Sample

#=={}||Det[#.Transpose@#]!=0&@{{1,2,3},{1,3,5},{0,0,0}}
>>  False

Answer 8

JavaScript (ES6), 162

M=>M.sort((a,b)=>P(a)-P(b),P=r=>r.findIndex(v=>v)).map(_=>M=M.map((r,i)=>(p=P(r))>q?(k=M[i],q=p,r):r.map((v,j)=>v*k[q]-k[j]*r[p]),q=-1))&&M.every(r=>r.some(v=>v))

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

Less golfed

M=>(
  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.sort((a,b)=>P(a)-P(b)), 
  M.map(_=> // repeat transformation for the number of rows
    M=M.map((r,i)=>(
      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])
     )
     ,q=-1
    )
  ),
  // return false if there are rows all 0 or all NaN
  M.every(r=>r.some(v=>v))
)

Test

F=M=>M.sort((a,b)=>P(a)-P(b),P=r=>r.findIndex(v=>v))
.map(_=>M=M.map((r,i)=>
(p=P(r))>q?(k=M[i],q=p,r):r.map((v,j)=>v*k[q]-k[j]*r[p])
,q=-1))&&M.every(r=>r.some(v=>v))
  
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
].forEach(m=>console.log(m,F(m)))

<pre id=O></pre>

Answer 9

MATL, 13 11 bytes

t!Y*2$0ZnYo

Thanks to Luis for golfing off two bytes.

Based on Anna's MATLAB answer.

Explanation

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

Answer 10

Python 2 with NumPy - 85 112 103 102 bytes

import numpy
x=input(i)
try:print reduce(lambda a,b:a*b,numpy.linalg.eigvals(x))
except:print(x==[])|0

Hopefully can get a few off, FGITW.

Answer 11

MATL, 33 bytes

|ssQt_w2$:GZy1)Z^!2$1!G*Xs!Xa~s3<

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

Input format is

[0 1; 2 3]

or

[[0 1];[2 3]]

Try it online!

Explanation

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 a₁, a₂, ... 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 a₁, a₂, ... between −S−1 and S+1 are tested. The input vectors v₁, v₂, ... are independent iff only one of the linear combinations a₁v₁+a₂v₂+... gives a 0 result (namely that for coefficients a₁, a₂, ... = 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

Answer 12

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 X^TX 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|X^TX| to get the result.

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

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

Made possible with help from Dennis!

Answer 13

Jelly, 5 2 bytes (non-competing)

ÆḊ

Try it online!