6
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Can we take the set of vectors as a rectangular matrix? \$\endgroup\$ – Alex A. Apr 19 '16 at 22:52
  • 2
    \$\begingroup\$ May we call a determinant built-in? \$\endgroup\$ – xnor Apr 19 '16 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 Apr 19 '16 at 23:11
  • 9
    \$\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 Apr 19 '16 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 Apr 19 '16 at 23:25

13 Answers 13

5
\$\begingroup\$

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 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!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\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 Apr 20 '16 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 Apr 20 '16 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 Apr 20 '16 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 Apr 20 '16 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. Apr 21 '16 at 2:44
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

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

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>

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ What is the significance of the |0 in the final line? \$\endgroup\$ – orlp Apr 20 '16 at 15:33
1
\$\begingroup\$

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 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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
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!

| improve this answer | |
\$\endgroup\$
  • \$\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 Apr 27 '16 at 21:59
1
\$\begingroup\$

Jelly, 5 2 bytes (non-competing)

ÆḊ

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 1. Both determinant and matrix multiplication have been implemented after this challenge were posted. You should state that your answer is non-competing. 2. 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 Apr 25 '16 at 14:22
  • \$\begingroup\$ Determinant is allowed. \$\endgroup\$ – Leaky Nun Apr 25 '16 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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