# How do I reduce to a basis?

I'm doing some computation with symbols X, Y, Z, XX, XY, ..., which are linearly independent elements in some larger vector space. For example, consider the following simple set:

set = {X, Y, X + Y, X + Z, 2 X + Z}


I would like to obtain a basis of the subspace V = Span(set) so that this basis is a subset of Set obtained by going through the list and removing those elements that are linear combinations of those that we already picked. The output for this simple example should by {X, Y, X + Z}.

Is there a quick way of doing this simply by converting to vectors, finding a basis, and converting the answer back to set elements?

Edit 1. The set above is just an example. In my computations it can have 100s of elements.

• GroebnerBasis[{x, y, x + y, x + z, 2*x + z}, {x, y, z}] produces an equivalent basis {z, y, x}. – user64494 Jan 22 at 14:26
• Thanks but I really want a subset of Set. – Astro Naut Jan 22 at 14:37
• Set is a protected system symbol. Generally most users avoid using capitals to start their own symbol and function names. – Michael E2 Jan 22 at 15:00
• Thanks Michael E2. changed Set -> set – Astro Naut Jan 22 at 15:07

One of the things I remember from my linear algebra class in 1983:

set = {X, Y, X + Y, X + Z, 2 X + Z};

Extract[set,
FirstPosition[#, 1, Nothing] & /@
RowReduce@Transpose@CoefficientArrays[set, Variables@set][[2]]
]

(*  {X, Y, X + Z}  *)

• Great. Thanks for the answer! – Astro Naut Jan 22 at 15:17
• @user76928 You're welcome! :) – Michael E2 Jan 22 at 15:18
• Can this be generalized to the case where the elements of set are matrices or even tensors of variables? – ala10 Jan 22 at 15:36
• @user64494 Unfortunately for your example, Z^2 seems to be nonsense according to the question. – Michael E2 Jan 22 at 15:50
• @user64494 The square of a vector in a vector space is undefined. Only (homogeneous) linear combinations of the variables are permitted. – Michael E2 Jan 22 at 16:46

As long as you are just working with vectors, you can use RowReduce to remove linearly dependent elements in set.

set = {X, Y, X + Y, X + Z, 2 X + Z}


you can, assuming X, Y and Z are some vectors in a vector space, define associated vectors via

setVecs = set /. {X -> {1, 0, 0}, Y -> {0, 1, 0}, Z -> {0, 0, 1}}


Edit: As suggested in the comments, this can be automated, e.g. via

 setVecs = set /. With[{vars = Variables[set]},
MapIndexed[Rule[#1, UnitVector[Length@vars, First@#2]] &, vars]]


Since

MatrixRank[setVecs]

 3


we need to remove two elements. Which ones to remove can be found by looking at the pivots of

rr = setVecs // Transpose // RowReduce

{{1, 0, 1, 0, 1},
{0, 1, 1, 0, 0},
{0, 0, 0, 1, 1}}


The third element is therefore a linear combination of the first two, and the fifth element is the sum off the first and fourth element of set. To get the basis element positions in set we can use

basisElements = Flatten[FirstPosition[#, 1, Nothing] & /@ rr]

{1, 2, 4}


The associated elements of set can then be extracted via

basis = set[[basisElements]]]

{X, Y, X + Z}

• That is done by hand with help of Mathematica. Think of higher dimensions, say 1024. – user64494 Jan 22 at 14:51
• But I have no control what's in Sets (an output of some computation). It can have 100s of elements. – Astro Naut Jan 22 at 14:57
• That should not be a problem, collect all variables X, Y, Z, etc., replace them with some basis vectors, and the steps after that should work exactly the same – Hausdorff Jan 22 at 14:58
• The approach in this answer can be generalized with something like set /. With[{vars = Variables[set]}, Thread[vars -> IdentityMatrix[Length[vars]]]]. – J. M.'s ennui Jan 22 at 14:59
• UnitVector[k] could also be used. – Michael E2 Jan 22 at 15:10