1
$\begingroup$

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!

$\endgroup$
6
  • 2
    $\begingroup$ The null space doesn't uniquely determine a matrix. I'm confused by this question! Can you offer more details? $\endgroup$
    – march
    Nov 20 '15 at 21:10
  • $\begingroup$ I'm not trying to state that I would like a unique matrix with a given nullspace. I'm trying to ask, how can I find some matrix, with the unique given nullspace. So any matrix having those vectors as its basis for the nullspace would do. Sorry for the confusion. $\endgroup$
    – user238194
    Nov 20 '15 at 21:12
  • 1
    $\begingroup$ v = RandomInteger[{1, 3}, {3, 4}]; m = Array[mi, {4, 4}]; s = Solve[m.# == 0 & /@ v][[1]]; s /. Thread[Variables@Tr[Last /@ s] -> 1] $\endgroup$ Nov 20 '15 at 21:40
  • 1
    $\begingroup$ You could build the matrix of the projection on the orthogonal of the span of the $n$ given vectors. $\endgroup$
    – anderstood
    Nov 20 '15 at 22:38
  • 2
    $\begingroup$ Take the null space of the vectors. $\endgroup$ Nov 20 '15 at 23:28
1
$\begingroup$

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])}} *)
$\endgroup$
1
$\begingroup$

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]}

enter image description here

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.

$\endgroup$

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.