# NullSpace is very slow over number fields

I have a $$20 \times 20$$ matrix $$M$$ with coefficients in $$\mathbf{Q}(\sqrt{5})$$ but Mathematica is unable to compute the null space (or at least is incredibly slow in doing so). [In the case of interest the null space has dimension exactly one.] Although the coefficients are moderately large, this is not a very difficult computation; if forced do I could make mathematica do it by hand simply by writing down the $$20$$ linear equations and eliminating the variables one by one. So clearly whatever Mathematica is doing after I type:

NullSpace[M]

is pretty stupid. What am I doing wrong?

An example:

M:={{1/Sqrt[5], 1, 0, 0, 0, 0, (27 + 25*Sqrt[5])/125,
1/Sqrt[5], 0, 0, 0, 0, (3*(675 + 467*Sqrt[5]))/3125,
(27 + 25*Sqrt[5])/125, 0, 0, 0, 0},
{(27 + 25*Sqrt[5])/250, 1/Sqrt[5], 1, 0, 0, 0,
(3*(675 + 467*Sqrt[5]))/6250, (27 + 25*Sqrt[5])/125,
1/Sqrt[5], 0, 0, 0, (12*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/3125, (27 + 25*Sqrt[5])/125,
0, 0, 0}, {(675 + 467*Sqrt[5])/6250,
(27 + 25*Sqrt[5])/250, 1/Sqrt[5], 1, 0, 0,
(4*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/6250, (27 + 25*Sqrt[5])/125,
1/Sqrt[5], 0, 0, (2*(73925 + 42339*Sqrt[5]))/78125,
(12*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/3125, (27 + 25*Sqrt[5])/125,
0, 0}, {(1583 + 970*Sqrt[5])/15625,
(675 + 467*Sqrt[5])/6250, (27 + 25*Sqrt[5])/250,
1/Sqrt[5], 1, 0, (73925 + 42339*Sqrt[5])/156250,
(4*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/6250, (27 + 25*Sqrt[5])/125,
1/Sqrt[5], 0, (3*(69351 + 38035*Sqrt[5]))/78125,
(2*(73925 + 42339*Sqrt[5]))/78125,
(12*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/3125, (27 + 25*Sqrt[5])/125,
0}, {(73925 + 42339*Sqrt[5])/781250,
(1583 + 970*Sqrt[5])/15625, (675 + 467*Sqrt[5])/
6250, (27 + 25*Sqrt[5])/250, 1/Sqrt[5], 1,
(3*(69351 + 38035*Sqrt[5]))/390625,
(73925 + 42339*Sqrt[5])/156250,
(4*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/6250, (27 + 25*Sqrt[5])/125,
1/Sqrt[5], (42*(4089250 + 2175827*Sqrt[5]))/
48828125, (3*(69351 + 38035*Sqrt[5]))/78125,
(2*(73925 + 42339*Sqrt[5]))/78125,
(12*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/3125, (27 + 25*Sqrt[5])/
125}, {(69351 + 38035*Sqrt[5])/781250,
(73925 + 42339*Sqrt[5])/781250,
(1583 + 970*Sqrt[5])/15625, (675 + 467*Sqrt[5])/
6250, (27 + 25*Sqrt[5])/250, 1/Sqrt[5],
(7*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/390625,
(73925 + 42339*Sqrt[5])/156250,
(4*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/6250, (27 + 25*Sqrt[5])/125,
(84*(12928009 + 6726315*Sqrt[5]))/244140625,
(42*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/78125,
(2*(73925 + 42339*Sqrt[5]))/78125,
(12*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/3125},
{(4089250 + 2175827*Sqrt[5])/48828125,
(69351 + 38035*Sqrt[5])/781250,
(73925 + 42339*Sqrt[5])/781250,
(1583 + 970*Sqrt[5])/15625, (675 + 467*Sqrt[5])/
6250, (27 + 25*Sqrt[5])/250,
(12*(12928009 + 6726315*Sqrt[5]))/244140625,
(7*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/390625,
(73925 + 42339*Sqrt[5])/156250,
(4*(1583 + 970*Sqrt[5]))/15625,
(3*(675 + 467*Sqrt[5]))/6250,
(36*(923887075 + 472444731*Sqrt[5]))/6103515625,
(84*(12928009 + 6726315*Sqrt[5]))/244140625,
(42*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/78125,
(2*(73925 + 42339*Sqrt[5]))/78125,
(12*(1583 + 970*Sqrt[5]))/15625},
{(3*(12928009 + 6726315*Sqrt[5]))/488281250,
(4089250 + 2175827*Sqrt[5])/48828125,
(69351 + 38035*Sqrt[5])/781250,
(73925 + 42339*Sqrt[5])/781250,
(1583 + 970*Sqrt[5])/15625, (675 + 467*Sqrt[5])/
6250, (9*(923887075 + 472444731*Sqrt[5]))/
12207031250, (12*(12928009 + 6726315*Sqrt[5]))/
244140625, (7*(4089250 + 2175827*Sqrt[5]))/
48828125, (3*(69351 + 38035*Sqrt[5]))/390625,
(73925 + 42339*Sqrt[5])/156250,
(4*(1583 + 970*Sqrt[5]))/15625,
(18*(441931153 + 222896176*Sqrt[5]))/1220703125,
(36*(923887075 + 472444731*Sqrt[5]))/6103515625,
(84*(12928009 + 6726315*Sqrt[5]))/244140625,
(42*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/78125,
(2*(73925 + 42339*Sqrt[5]))/78125},
{(923887075 + 472444731*Sqrt[5])/12207031250,
(3*(12928009 + 6726315*Sqrt[5]))/488281250,
(4089250 + 2175827*Sqrt[5])/48828125,
(69351 + 38035*Sqrt[5])/781250,
(73925 + 42339*Sqrt[5])/781250,
(1583 + 970*Sqrt[5])/15625,
(2*(441931153 + 222896176*Sqrt[5]))/1220703125,
(9*(923887075 + 472444731*Sqrt[5]))/12207031250,
(12*(12928009 + 6726315*Sqrt[5]))/244140625,
(7*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/390625,
(73925 + 42339*Sqrt[5])/156250,
(121*(385679275 + 192348757*Sqrt[5]))/6103515625,
(18*(441931153 + 222896176*Sqrt[5]))/1220703125,
(36*(923887075 + 472444731*Sqrt[5]))/6103515625,
(84*(12928009 + 6726315*Sqrt[5]))/244140625,
(42*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/78125},
{(441931153 + 222896176*Sqrt[5])/6103515625,
(923887075 + 472444731*Sqrt[5])/12207031250,
(3*(12928009 + 6726315*Sqrt[5]))/488281250,
(4089250 + 2175827*Sqrt[5])/48828125,
(69351 + 38035*Sqrt[5])/781250,
(73925 + 42339*Sqrt[5])/781250,
(121*(385679275 + 192348757*Sqrt[5]))/61035156250,
(2*(441931153 + 222896176*Sqrt[5]))/1220703125,
(9*(923887075 + 472444731*Sqrt[5]))/12207031250,
(12*(12928009 + 6726315*Sqrt[5]))/244140625,
(7*(4089250 + 2175827*Sqrt[5]))/48828125,
(3*(69351 + 38035*Sqrt[5]))/390625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
6103515625, (18*(441931153 + 222896176*Sqrt[5]))/
1220703125, (36*(923887075 + 472444731*Sqrt[5]))/
6103515625, (84*(12928009 + 6726315*Sqrt[5]))/
244140625, (42*(4089250 + 2175827*Sqrt[5]))/
48828125}, {(11*(385679275 + 192348757*Sqrt[5]))/
61035156250, (441931153 + 222896176*Sqrt[5])/
6103515625, (923887075 + 472444731*Sqrt[5])/
12207031250, (3*(12928009 + 6726315*Sqrt[5]))/
488281250, (4089250 + 2175827*Sqrt[5])/48828125,
(69351 + 38035*Sqrt[5])/781250,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
61035156250, (2*(441931153 + 222896176*Sqrt[5]))/
1220703125, (9*(923887075 + 472444731*Sqrt[5]))/
12207031250, (12*(12928009 + 6726315*Sqrt[5]))/
244140625, (7*(4089250 + 2175827*Sqrt[5]))/
48828125, (156*(6161535913500 + 3020247065881*
Sqrt[5]))/95367431640625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
6103515625, (18*(441931153 + 222896176*Sqrt[5]))/
1220703125, (36*(923887075 + 472444731*Sqrt[5]))/
6103515625, (84*(12928009 + 6726315*Sqrt[5]))/
244140625}, {(102122106811 + 50456307775*Sqrt[5])/
1525878906250, (11*(385679275 + 192348757*Sqrt[5]))/
61035156250, (441931153 + 222896176*Sqrt[5])/
6103515625, (923887075 + 472444731*Sqrt[5])/
12207031250, (3*(12928009 + 6726315*Sqrt[5]))/
488281250, (4089250 + 2175827*Sqrt[5])/48828125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
61035156250, (2*(441931153 + 222896176*Sqrt[5]))/
1220703125, (9*(923887075 + 472444731*Sqrt[5]))/
12207031250, (12*(12928009 + 6726315*Sqrt[5]))/
244140625, (91*(59616582507451 + 29024686032265*
Sqrt[5]))/476837158203125,
(156*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
6103515625, (18*(441931153 + 222896176*Sqrt[5]))/
1220703125, (36*(923887075 + 472444731*Sqrt[5]))/
6103515625},
{(6161535913500 + 3020247065881*Sqrt[5])/
95367431640625, (102122106811 +
50456307775*Sqrt[5])/1525878906250,
(11*(385679275 + 192348757*Sqrt[5]))/61035156250,
(441931153 + 222896176*Sqrt[5])/6103515625,
(923887075 + 472444731*Sqrt[5])/12207031250,
(3*(12928009 + 6726315*Sqrt[5]))/488281250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
61035156250, (2*(441931153 + 222896176*Sqrt[5]))/
1220703125, (9*(923887075 + 472444731*Sqrt[5]))/
12207031250, (21*(1444965947772675 +
699351149175587*Sqrt[5]))/2384185791015625,
(91*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(156*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
6103515625, (18*(441931153 + 222896176*Sqrt[5]))/
1220703125},
{(59616582507451 + 29024686032265*Sqrt[5])/
953674316406250, (6161535913500 +
3020247065881*Sqrt[5])/95367431640625,
(102122106811 + 50456307775*Sqrt[5])/1525878906250,
(11*(385679275 + 192348757*Sqrt[5]))/61035156250,
(441931153 + 222896176*Sqrt[5])/6103515625,
(923887075 + 472444731*Sqrt[5])/12207031250,
(3*(1444965947772675 + 699351149175587*Sqrt[5]))/
4768371582031250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
61035156250, (2*(441931153 + 222896176*Sqrt[5]))/
1220703125, (48*(140340415946723 +
67573155118534*Sqrt[5]))/476837158203125,
(21*(1444965947772675 + 699351149175587*Sqrt[5]))/
2384185791015625,
(91*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(156*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
6103515625},
{(1444965947772675 + 699351149175587*Sqrt[5])/
23841857910156250,
(59616582507451 + 29024686032265*Sqrt[5])/
953674316406250, (6161535913500 +
3020247065881*Sqrt[5])/95367431640625,
(102122106811 + 50456307775*Sqrt[5])/1525878906250,
(11*(385679275 + 192348757*Sqrt[5]))/61035156250,
(441931153 + 222896176*Sqrt[5])/6103515625,
(16*(140340415946723 + 67573155118534*Sqrt[5]))/
2384185791015625,
(3*(1444965947772675 + 699351149175587*Sqrt[5]))/
4768371582031250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (121*(385679275 + 192348757*Sqrt[5]))/
61035156250, (1224*(18961264393923125 +
9088096183169283*Sqrt[5]))/1490116119384765625,
(48*(140340415946723 + 67573155118534*Sqrt[5]))/
476837158203125,
(21*(1444965947772675 + 699351149175587*Sqrt[5]))/
2384185791015625,
(91*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(156*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(66*(102122106811 + 50456307775*Sqrt[5]))/
762939453125},
{(140340415946723 + 67573155118534*Sqrt[5])/
2384185791015625, (1444965947772675 +
699351149175587*Sqrt[5])/23841857910156250,
(59616582507451 + 29024686032265*Sqrt[5])/
953674316406250, (6161535913500 +
3020247065881*Sqrt[5])/95367431640625,
(102122106811 + 50456307775*Sqrt[5])/1525878906250,
(11*(385679275 + 192348757*Sqrt[5]))/61035156250,
(153*(18961264393923125 + 9088096183169283*Sqrt[5]))/
2980232238769531250,
(16*(140340415946723 + 67573155118534*Sqrt[5]))/
2384185791015625,
(3*(1444965947772675 + 699351149175587*Sqrt[5]))/
4768371582031250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(6*(102122106811 + 50456307775*Sqrt[5]))/
762939453125, (153*(166244865882869551 +
79356955043968587*Sqrt[5]))/1490116119384765625,
(1224*(18961264393923125 + 9088096183169283*
Sqrt[5]))/1490116119384765625,
(48*(140340415946723 + 67573155118534*Sqrt[5]))/
476837158203125,
(21*(1444965947772675 + 699351149175587*Sqrt[5]))/
2384185791015625,
(91*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(156*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625},
{(9*(18961264393923125 + 9088096183169283*Sqrt[5]))/
2980232238769531250,
(140340415946723 + 67573155118534*Sqrt[5])/
2384185791015625, (1444965947772675 +
699351149175587*Sqrt[5])/23841857910156250,
(59616582507451 + 29024686032265*Sqrt[5])/
953674316406250, (6161535913500 +
3020247065881*Sqrt[5])/95367431640625,
(102122106811 + 50456307775*Sqrt[5])/1525878906250,
(9*(166244865882869551 + 79356955043968587*Sqrt[5]))/
1490116119384765625,
(153*(18961264393923125 + 9088096183169283*Sqrt[5]))/
2980232238769531250,
(16*(140340415946723 + 67573155118534*Sqrt[5]))/
2384185791015625,
(3*(1444965947772675 + 699351149175587*Sqrt[5]))/
4768371582031250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(13*(6161535913500 + 3020247065881*Sqrt[5]))/
95367431640625,
(342*(2027018218877988550 + 964069325712102763*
Sqrt[5]))/37252902984619140625,
(153*(166244865882869551 + 79356955043968587*
Sqrt[5]))/1490116119384765625,
(1224*(18961264393923125 + 9088096183169283*
Sqrt[5]))/1490116119384765625,
(48*(140340415946723 + 67573155118534*Sqrt[5]))/
476837158203125,
(21*(1444965947772675 + 699351149175587*Sqrt[5]))/
2384185791015625,
(91*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125},
{(166244865882869551 + 79356955043968587*Sqrt[5])/
2980232238769531250,
(9*(18961264393923125 + 9088096183169283*Sqrt[5]))/
2980232238769531250,
(140340415946723 + 67573155118534*Sqrt[5])/
2384185791015625, (1444965947772675 +
699351149175587*Sqrt[5])/23841857910156250,
(59616582507451 + 29024686032265*Sqrt[5])/
953674316406250, (6161535913500 +
3020247065881*Sqrt[5])/95367431640625,
(19*(2027018218877988550 + 964069325712102763*
Sqrt[5]))/37252902984619140625,
(9*(166244865882869551 + 79356955043968587*Sqrt[5]))/
1490116119384765625,
(153*(18961264393923125 + 9088096183169283*Sqrt[5]))/
2980232238769531250,
(16*(140340415946723 + 67573155118534*Sqrt[5]))/
2384185791015625,
(3*(1444965947772675 + 699351149175587*Sqrt[5]))/
4768371582031250,
(7*(59616582507451 + 29024686032265*Sqrt[5]))/
476837158203125,
(38*(19795470134413242383 + 9383950295224413485*
Sqrt[5]))/37252902984619140625,
(342*(2027018218877988550 + 964069325712102763*
Sqrt[5]))/37252902984619140625,
(153*(166244865882869551 + 79356955043968587*
Sqrt[5]))/1490116119384765625,
(1224*(18961264393923125 + 9088096183169283*
Sqrt[5]))/1490116119384765625,
(48*(140340415946723 + 67573155118534*Sqrt[5]))/
476837158203125,
(21*(1444965947772675 + 699351149175587*Sqrt[5]))/
2384185791015625}}

• Include your matrix as Mathematica code Sep 1, 2022 at 0:45
• Try NullSpace[M, Method->"OneStepRowReduction"], or test other methods
– I.M.
Sep 1, 2022 at 1:39
• @I.M. Thanks. You are not obliged to, but if you (or anyone else) could expand on that comment it would be close to what I am looking for. Namely, I'm looking for some explanation of what the default method is, why that was chosen, and why it is so very bad in this situation. Sep 17, 2022 at 14:13

You may calculate the eigenvalues of M:

Eigenvalues[M]


You see that the last eigenvalue is the one in question. We need therefore only calculate the last eigenvector:

Eigenvectors[M, -1]


(* {{(23742400000
(-44539357025075674109594672476002461125173771809612416197825771541721
8930832173906528779986639150333467331307242731840397363589515271585524
7432508190208832062466331404768799468408887785014511132296509537998405
76685760237335592040701764739282125713495359189341652952823 + ...
... ..*)

This gives a lengthy output because you are using accurate numbers.

You may speed up the calulation a lot if you use machine numbers. E.g.:

Eigenvectors[M // N, -1]


• Thanks for your answer. The reason I am not accepting it is that it doesn't explain why the most obvious thing to do works very badly. Clearly from a mathematical point of view first computing all the eigenvalues and then finding the eigenvector with eigenvalue 0 is at least as hard as computing the null space. Understanding why mathematica is so very slow would help in other situations. Sep 17, 2022 at 14:17
• You are wrong. I only used the "Eigenvalues" function for convenience. Getting an Eigenvector for a known Eigenvalue is easy. Start with a random vector. Multiply this vector by the matrix. This deletes the part belonging to eigenvalue zero. Therefore the missing direction is an eigenvalue to eigenvalue zero. For other eigenvalues one need to shift all the eigenvalues of the matrix. Sep 17, 2022 at 15:23
• You are wrong. Computing the null space is exactly the same as computing the eigenspace with eigenvalue zero. They are mathematically equivalent. So obviously what I said is correct. The way to compute the eigenspace with eigenvalue $\lambda$ is exactly to compute the null space of $M - \lambda$. Also what you say about how to compute eigenvectors is nonsense, the "missing direction" is not defined. If $M$ is a $2 \times 2$ matrix with one eigenvalue $0$ and and $Mv = (1,0)$ for some $v$, what is the "missing direction"? The nullspace could be $(\eta,1)$ for any value of $\eta$. Sep 17, 2022 at 18:02