Finding matrix given null space

Question

Suppose I input a very large $n$ integer vectors and I wish to compute the matrix whose nullspace is spanned uniquely by these vectors. Is there an appropriate command/module to do this using mathematica?

Thanks!

Answer 1

After Reading anderstoods Comment on the Original Post

I realized that I had actually constructed the projector on the space orthogonal to the span of the vectors. This led me to the simpler version. Again, if you know that your vectors are linearly independent, you don't have to kick out the vectors. But I like orthogonalizing first.

v = N@RandomInteger[10, {3, 5}];
dim = Length@First@v;
vO = DeleteCases[Orthogonalize@nulls, ConstantArray[0, dim]];
dimNull = Length@vO;

Then:

mat = IdentityMatrix[dim] - Plus @@ Map[Outer[Times, #, #] &, vO]

Modest Generalization

We'll take as our list of vectors spanning the null space to be

v = N@RandomInteger[10, {3, 5}];
dim = Length@First@v;

I'm not sure about your case, but there's the possibility that this set of vectors is not minimal, so we orthogonalize them and kick out any zero vectors:

vO = DeleteCases[Orthogonalize@v, ConstantArray[0, dim]];
dimNull = Length@vO;

We then construct a basis by adding to this last of vectors the unit basis for the space, orthogonalize, and drop any zero vectors (of which there will definitely be some).

basis = Drop[Orthogonalize@Join[vO, IdentityMatrix[dim]] // Chop, -dimNull];

Finally, construct the diagonalized matrix,

d = DiagonalMatrix[Table[If[jj <= dimNull, 0, 1], {jj, dim}]];

and transform back to the "original" basis:

mat = Transpose[#].d.# &@basis;

Finally, check to make sure that it works:

mat.# & /@ basis // Chop

(which it does).

Original Post

Your statement that you have "a very large $n$ integer vectors" makes me think that the following solution won't work, in the sense that it's probably computationally expensive. There's a part of it that's also not automated, but at least it's a start.

We'll use as an example null space,

nuls = {{1, 1, 1}, {1, 0, 1}};

We first orthogonalize this set of vectors to get an orthonormal basis for the null space:

nulsO = Orthogonalize@nuls
(* {{1/Sqrt[3], 1/Sqrt[3], 1/Sqrt[3]}, {1/Sqrt[6], -Sqrt[(2/3)], 1/Sqrt[6]}} *)

We then have to extend this basis to a basis on the entire space. Off the top of my head, I can't remember any algorithms for generating this extension (although I know that it's straightforward), so we will do it by hand:

basis = Orthogonalize[Join[nulsO, {{1,0,0}}]
(* {{1/Sqrt[3], 1/Sqrt[3], 1/Sqrt[3]}, {1/Sqrt[6], -Sqrt[(2/3)], 1/Sqrt[6]}, {1/Sqrt[2], 0, -(1/Sqrt[2])}} *)

Now, the meat of the problem. The insight here is to note that in the eigenbasis of the matrix we are constructing, there will be 2 ($n$ in the general case) diagonal entries that are zero, and the rest should be non-zero. Since the matrix is unique, we have freedom to choose, so we choose as our matrix

d = DiagonalMatrix[Table[If[jj <= Length@nullSpace, 0, 1], {jj, Length@nullSpace[[1]]}]]
(* {{0, 0, 0}, {0, 0, 0}, {0, 0, 1}} *)

In other words, we choose the matrix to have $n$ zeros along the diagonal and the rest 1's. Finally, we use our basis of eigenvectors to transform back into the original space. Since we chose an orthonormal basis, this is straight-forward:

mat = Transpose[basis].d.basis
(* {{1/2, 0, -(1/2)}, {0, 0, 0}, {-(1/2), 0, 1/2}} *)

To check that we have succeeded, apply this matrix to the basis one vector at a time:

mat.# & /@ basis
(* {{0, 0, 0}, {0, 0, 0}, {1/Sqrt[2], 0, -(1/Sqrt[2])}} *)

Answer 2

Say you have two vectors (I'll just make length-5 for demonstration) concatenated into a matrix a.

a = RandomInteger[{0, 10}, {5, 2}];
m = NullSpace[Transpose[a]];
{MatrixForm[m], MatrixForm[a]}

The Matrix m contains rows that are orthogonal to the two vectors, as you can see since

 m.a 

is the zero matrix. Hence m is a matrix whose null space is the columns of a.