What is the Subspace Dimension?

Question

Challenge

Given the Cartesian coordinates of two or more distinct points in Euclidean n-space (\$\mathbb{R}^n\$), output the minimum dimension of a flat (affine) subspace that contains those points, that is 1 for a line, 2 for a plane, and so on.

For example, in 3-space (the 3-dimensional world we live in), there are a few possibilities:

1. The points are not coplanar, e.g. (0,0,0),(0,0,1),(0,1,0),(1,0,0). The full 3 dimensions would be needed to describe the points, so the output would be 3
2. The points are coplanar but not all collinear, e.g. (0,0,0),(1,0,0),(0,1,0),(1,1,0). The points lie on a 2-dimensional surface (a plane), so the output would be 2.
3. The points are collinear, and there is more than one, e.g. (0,0,0),(1,0,0). They all lie on a line (1-dimensional), so the output is 1.
4. One or zero points are given. You do not have to handle these degenerate cases.

As @user202729 pointed out in sandbox, this is equivalent to the rank of the matrix whose column vectors are the given points if one of the points is the zero vector.

I encourage upvoting answers that don't have built-ins do most of the work, but they are valid answers.

Details

1. The coordinates of each point will always be integers, so errors due to excessive floating-point roundoff are not acceptable
2. Again, you do not have to handle fewer than 2 points
3. The dimension n will be at least 2
4. The set of points can be taken in any format that encodes equivalent information to a list of n-tuples. Your program/function may also take n as input if you desire.
5. Note that the subspace may not necessarily pass through the origin*
6. This is code-golf, so shortest bytes wins

*Mathematically, if we require the subspace to pass through the origin, then it would be more specifically called a "linear subspace", not just flat.

Testcases

n points -> output
2 (1,0),(0,0) -> 1
2 (0,1),(0,0) -> 1
2 (6,6),(0,-2),(15,18),(12,14) -> 1
2 (0,0),(250,500),(100001,200002) -> 1
2 (0,0),(250,500),(100001,200003) -> 2
2 (3,0),(1,1),(1,0) -> 2
3 (0,0,0),(0,0,1),(0,1,0),(1,0,0) -> 3
3 (0,0,0),(1,0,0),(0,1,0),(1,1,0) -> 2
3 (0,0,0),(1,0,0) -> 1
4 (1,2,3,4),(2,3,4,5),(4,5,6,7),(4,4,4,4),(3,3,3,3),(2,2,2,2) -> 2
5 (5,5,5,5,5),(5,5,6,5,5),(5,6,5,5,5),(6,5,5,5,5),(5,4,3,2,1) -> 4

Related Challenges:

• Is the matrix rank one?
• Linear Independence.

Answer 1

Wolfram Language (Mathematica), 23 bytes

MatrixRank@*Differences

Try it online!

Alternative: (23 bytes, 21 characters)

MatrixRank[#&@@#-#]&

Try it online!

SingularValueDecomposition in Mathematica is already 26 bytes long.

Answer 2

MATL, 12 bytes

t1Y)-X$&Yvoz

Input is a matrix, where each row defines a point.

Try it online! Or verify all test cases.

Explanation

The code uses the singular value decomposition of a matrix, which is done symbolically to prevent floating-point issues. The rank of a matrix equals the number of non-zero singular values.

t      % Implicit input: matrix of integer values. Duplicate
1Y)    % Get the first row
-      % Subtract, with broadcast. This subtracts this row from each row
X$     % Convert to symbolic matrix. Note that integers, are represented
       % exactly as floating-point values up to ±2^53.
&Yv    % Single-output singular value decomposition. Gives a vector with
       % the singular values
o      % Convert to floating point. Note that 0 is represented exactly
       % as a floating-point value
z      % Number of nonzeros. Implicit output

Answer 3

APL (Dyalog Unicode), 17 bytes

≢⍸1≠1+2⊃8415⌶2-⌿⎕

Try it online!

Happens to be a mix of existing MATL and Mathematica solutions. Performs Singular Value Decomposition on pairwise differences of the rows, and counts nonzero eigenvalues in the result of SVD. Since APL does not have symbolic computation, we use "significantly different from zero" test instead.

How it works

≢⍸1≠1+2⊃8415⌶2-⌿⎕
             2-⌿⎕  ⍝ Pairwise row differences of the input
      2⊃8415⌶      ⍝ The second matrix (diagonal matrix of eigenvalues) in SVD
  1≠1+             ⍝ Check if each number is significantly different from zero
≢⍸                 ⍝ Count ones

Answer 4

Julia 0.7, 18 bytes

m->rank(m.-m[:,1])

Try it online!

Analogous approach in R is slightly longer (3 bytes saved by Giuseppe):

R, 27 24 bytes

function(m)qr(m-m[,1])$r

Try it online!

Answer 5

JavaScript (ES6), 187 bytes

There's probably a much shorter way. This is using the matrix rank method.

m=>m[m=m.map(r=>r.map((v,i)=>v-m[0][i])),n=0].map((_,i)=>(R=m.find((r,k)=>r[i]&&r[j=~k]^(r[j]=1)))&&m.map(r=>++j*r[i]&&R.map((v,k)=>r[k]-=k>i&&v*r[i]),n++,R=R.map((v,k)=>k>i?v/R[i]:v)))|n

Try it online!