Subspaces in Mathematica

Question

I'm working on a research project and I need to learn how to use Mathematica to calculate subspaces. Specifically I plan to solve the following operations and I would greatly appreciate if you could give me an example of how to solve it.

For example:

1. In the vector space $Ρ^n$, consider the sub space

   $$S = \left\langle(1, -2,1,0, ..., 0), (0,1, -2,1,0, ..., 0) ... (0,0, ..., 1, -2,1)\right\rangle$$

   Calculate equations defining $S$ for $n = 4, 8, 16, 20$.

2. Find generator subspaces of "magic" matrices of $2\times2$, $3\times3$ and $4\times4$ (a square matrix is called magic if the sums of the elements in each row, each column and in the diagonal are always the same)

Answer 1

Both questions ask to find bases for the kernels (null spaces) of matrices.

The first one asks for the kernel of $S(n)$ where, in Mathematica, $S(n)$ can be created as

s[n_Integer] /; n >= 3 := 
  SparseArray[{Band[{1, 1}] -> -1,  Band[{1, 2}] -> 2, Band[{1, 3}] -> -1}, {n - 2, n}];

For instance,

NullSpace[s[4]]

returns

{{-2, -1, 0, 1}, {3, 2, 1, 0}}

This means that every linear combination $(s_1, s_2, s_3, s_4)$ of rows of $S(4)$ satisfies two linear equations: $-2s_1 - s_2 + s_4=0$ and $3s_1+2s_2+s_3=0$ and, conversely, that every 4-vector satisfying these two equations can be written as a linear combination of rows of $S(4)$.

There are two aspects to the second question. The first is to recognize that the constant (to which all the sums are equal) should be considered as a variable, along with the $n^2$ entries in the magic square of order $n$. This casts the question as giving a set of $n + n + 2$ equations in $n^2+1$ coefficients. The "generator subspace" of the solution is the nullspace.

I will present a slightly inefficient solution because (a) only small matrices are involved, so computational efficiency is unimportant and (b) pieces of the solution may be of interest in their own right. Thus, the following code first ignores the last variable and generates the defining equations in a way that clearly parallels the statement of the problem:

magic[n_Integer] /; n >= 1 := 
 Module[{index, rowSums, colSums, diagonal, invDiagonal},
  index = Function[{i, j}, (i - 1) n + j];
  rowSums = Table[{i, index[i, #]} -> 1 & /@ Range[n], {i, Range[n]}] // Flatten;
  colSums = Table[{i + n, index[#, i]} -> 1 & /@ Range[n], {i, Range[n]}] // Flatten;
  diagonal = {2 n + 1, index[#, #]} -> 1 & /@ Range[n];
  invDiagonal = {2 n + 2, index[n + 1 - #, #]} -> 1 & /@ Range[n];
  SparseArray[rowSums~Join~colSums~Join~diagonal~Join~invDiagonal]
  ]

For example,

magic[2] // MatrixForm

gives

$$\left( \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array} \right)$$

The columns correspond to the $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$ entries in a two by two matrix $\mathbb{M} = \left(m_{ij}\right)$, respectively. Thus, for instance, the last row $(0,1,1,0)$ corresponds to the linear combination $m_{12} + m_{21}$, which is the sum along its inverse diagonal.

The full set of equations can be obtained by joining a column of $-1$s:

With[{n = 2}, Join[magic[n], ConstantArray[{-1}, 2 n + 2], 2]]

Once again, invoke NullSpace to find a set of generators of the solutions:

% // NullSpace

{{1, 1, 1, 1, 2}}

That is, the only two by two magic matrices are scalar multiples of $\left( \begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array} \right)$. Moreover, if one seeks an integral solution, the final $2$ shows that the common row, column, and diagonal sums must be even.

Answer 2

A)

basis[std_, n_] := 
   If[n < Length[std], "Invalid specs", 
      With[{null = ConstantArray[0, n - Length[std]}, 
          Flatten /@ Permutations[Prepend[null, std]]]]
eqn[n_ /; (IntegerQ[n] && NonNegative[n])] := Array[x^(# - 1) &, n]
combine[std_, n_] := eqn[n].# & /@ basis[std, n]
TableForm[Table[Row[{ToString[k] <> "->", combine[{1, -2, 1}, k]}],
   {k, {4, 8, 16, 20}}], TableDepth -> 1]

Gives:

(*  
4->{1-2 x+x^2,x-2 x^2+x^3}    
8->{1-2 x+x^2,x-2 x^2+x^3,x^2-2 x^3+x^4,x^3-2 x^4+x^5,x^4-2 x^5+x^6,x^5-2 x^6+x^7}    
16->{1-2 x+x^2,x-2 x^2+x^3,x^2-2 x^3+x^4,x^3-2 x^4+x^5,x^4-2 x^5+x^6,...}    
20->{1-2 x+x^2,x-2 x^2+x^3,x^2-2 x^3+x^4,x^3-2 x^4+x^5,x^4-2 x^5+x^6,...}
*)

---

B) I have never encountered the term "generator subspace" before. Do you simply want a function that generates magic matrices? By generator subspaces, do you mean the column space of the magic matrix?