Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
rref, lu and matrix arrangements

Subject: rref, lu and matrix arrangements

From: matt

Date: 22 May, 2011 11:19:12

Message: 1 of 9

Dear all,

let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
where B1 is pxr and B2 is qxr.

Now, consider the case in which another basis of null(A) exists that can
be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
C12 is pxu, C22 is qxu and C23 is qxv.

Is there any algorithm which, when possible, returns
[C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?

I've tried to implement an algorithm which relies on rref and lu
factorization, but I have some test cases in which it doesn't work.

Is it reasonable to expect to solve this problem? Can you provide some
suggestions?

Thanks in advance

--
Matteo

Subject: rref, lu and matrix arrangements

From: Daniel Lichtblau

Date: 22 May, 2011 22:25:31

Message: 2 of 9

On May 22, 6:19 am, matt <n...@none.com> wrote:
> Dear all,
>
> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
> where B1 is pxr and B2 is qxr.
>
> Now, consider the case in which another basis of null(A) exists that can
> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
> C12 is pxu, C22 is qxu and C23 is qxv.
>
> Is there any algorithm which, when possible, returns
> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>
> I've tried to implement an algorithm which relies on rref and lu
> factorization, but I have some test cases in which it doesn't work.
>
> Is it reasonable to expect to solve this problem? Can you provide some
> suggestions?
>
> Thanks in advance
>
> --
> Matteo

Will depend on dimensions. Your t should be perhaps p, or at least not
larger, for example.

This might be along the lines you seek. I'll show an example with
Mathematica but
the code should translate readily to Matlab or other languages.

Create a random 7x16 matrix.

mat = RandomReal[{-10, 10}, {7, 16}];

Find, and row reduce, the null space.

nulls = NullSpace[mat];
rednulls = RowReduce[nulls];

We'll use p=4 and q=3.

p = 4;
q = Length[nulls] - p;

The bottom part, your [0,C22,C23] section, is easy.

bottom = Drop[rednulls, p];

We'll use the rest as our top part, and make alterations to get zeros
at the right end.

top = Take[rednulls, p];

From the description, you perhaps got this far. To do the rest, first
reverse the null vectors in 'bottom', row reduce, and reverse back. We
get a set of null vectors that is in echelon form columnwise from
right-to-left.

bottom2 = Map[Reverse, RowReduce[Map[Reverse, bottom]]];

Use this to zero the 'top' null vectors on the right side.

Do[top[[j]] = top[[j]] - top[[j, -k]]*bottom2[[k]], {j,
  Length[top]}, {k, Length[bottom2]}]

Here is the result in this example. Notice 'top' is now zerod on the
right.

In[116]:= top

Out[116]= {{1., 0., 0., 0., -0.1570521698815333, -0.1438145481730163,
  0.3341102247948281, 1.159540140238518, 0.2594884364079637,
  0.3116479687035286, -0.3244619655034073, 0., 0., 0., 0., 0.}, {0.,
  1., 0., 0., -0.353199257121722, 0.3955447462849144,
  0.2770180465857701, 1.051468466698785, 0.1646042200361716,
  1.289988509255458, -0.314174133729317, 0., 0., 0., 0., 0.}, {0., 0.,
   1., 0., 0.01528706008350322, -0.4786839021436973, \
-0.6380269892684085, 1.108257764338746, 0.4819835401333382,
  0.4796243014367019, -1.087136217299042, 0., 0., 0., 0., 0.}, {0.,
  0., 0., 1., 0.1905092618416806, 0.5196853394491601,
  0.756397394849917, -0.7050950551954204, -0.871705286441594, \
-0.9738372685877903, 0.8759900364217903, 0., 0., 0., 0., 0.}}

In[117]:= bottom

Out[117]= {{0, 0, 0, 0, 1, 0., 0., 0., 0., -0.5597664757073788,
  0.8143070871866038, 0.4277776146150173, -1.098944133145463,
  0.8081363401427031, -2.848613830703109, 1.872743300071011}, {0, 0,
  0, 0, 0, 1, 0., 0.,
  0., -0.4570234191081754, -0.1822057163418105, -1.020755390589715, \
-1.275200915927704, 0.4217003016771535, -0.3216906116940924,
  1.137607237636676}, {0, 0, 0, 0, 0, 0, 1, 0.,
  0., -2.057131526158108, 1.762612098425479,
  1.519296054797632, -1.391652167046286,
  0.3584888909059545, -3.946993942305765, 2.065619477936373}, {0, 0,
  0, 0, 0, 0, 0, 1, 0., -0.2846507307315486, 0.2895074106852998,
  0.4478459988247586, -1.530445195016555,
  1.163129348653568, -2.008261891031013, 1.445298232599805}, {0, 0, 0,
   0, 0, 0, 0, 0, 1,
  0.7013048464911343, -1.428978238780057, -1.569680138947566,
  0.4155594211966983, -1.988702096113409,
  0.9380405673096524, -1.404713184245211}}

We can check correctness by showing that the top and bottom are all
null vectors, and combine to have rank 9, the rank of the original
null space.

In[120]:= nullset = Join[top, bottom];

In[121]:= Max[Abs[mat.Transpose[nullset]]]

Out[121]= 1.332267629550188*10^-14

In[122]:= MatrixRank[nullset]

Out[122]= 9

Daniel Lichtblau
Wolfram Research

Subject: rref, lu and matrix arrangements

From: matt

Date: 24 May, 2011 08:04:23

Message: 3 of 9

On 05/23/2011 12:25 AM, Daniel Lichtblau wrote:
> On May 22, 6:19 am, matt<n...@none.com> wrote:
>> Dear all,
>>
>> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
>> where B1 is pxr and B2 is qxr.
>>
>> Now, consider the case in which another basis of null(A) exists that can
>> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
>> C12 is pxu, C22 is qxu and C23 is qxv.
>>
>> Is there any algorithm which, when possible, returns
>> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>>
>> I've tried to implement an algorithm which relies on rref and lu
>> factorization, but I have some test cases in which it doesn't work.
>>
>> Is it reasonable to expect to solve this problem? Can you provide some
>> suggestions?
>>
>> Thanks in advance
>>
>> --
>> Matteo
>
> Will depend on dimensions. Your t should be perhaps p, or at least not
> larger, for example.
>
> This might be along the lines you seek. I'll show an example with
> Mathematica but
> the code should translate readily to Matlab or other languages.

Dear Daniel,

first of all, thanks for time you took to reply.

Unfortunately, I'm not familiar with Mathematica and I may have missed
some crucial piece of your algorithm, but at first (also 2nd and 3rd)
glance, it looks like the approach I've used too.

I have a test case where my approach fails. I'd greatly appreciate if
you could do the test with your algorithm; in case you managed it to
work, I'll further investigate your approach to discover the differences
with mine.

Thanks in advance,

Matteo.

========================================================================
TEST CASE
=========

Let A be the following 16x18 matrix:

A = [0.15005,-0.4318,-0.4318,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.4318,-0.15005;...
-0.0479,0,0,0,0,0,0,-0.5,0,0,0,0,0,-1,0,0.4318,0,0.0479;...
0,-0.0479,-0.4797,0,0,0,0,0,0,0,0,0,0,0,-1,0.15005,-0.0479,0;...
0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
-0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.0682;...
0,-0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,-0.0682,0;...
0,0,0,0.15005,0,0,0,0,0,0,0,0,-1,0,0,0,0,-0.15005;...
0,0,0,0.2521,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.2521;...
0,0,0,0,0.2521,0,0,0,0,0,-0.1797,0,0,0,-1,0.15005,0.2521,0;...
0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.2682;...
0,0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,-0.2682,0;...
-0.8660254,0.5,0.5,0,0,0,0,-0.8660254,0,0,0,0,0,0,0,0,0.5,0.8660254;...
-0.5877853,0.8090170,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.8090170,0.5877853;...
0,0,0,0.5,-0.8660254,0,0,0,0,0,-0.8660254,0,0,0,0,0,-0.8660254,-0.5;...
0,0,0,0.8660254,0.5,0,0,0,0,0,0,0,0,0,0,0,0.5,-0.8660254];

and let B = [B1;B2] the following 18x7 matrix (p = 7, q = 11, r = 7), a
basis of A's kernel:

B = [-0.5773503,0,0,0,0,0,0;...
0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
0,0,0,0,0,0,0;...
-0.5773503,0,0,0,0,0,0;...
0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
0,-0.4674929,-0.1645678,-0.0222354,-0.0918726,0.3672059,-0.7814043;...
0,0.4589534,-0.5071254,-0.1336586,0.6822599,0.0935152,-0.2002428;...
0,0,0,0,0,0,0;...
0,-0.2514693,0.6927794,-0.2576987,0.6159429,0.1043717,-0.0114939;...
0,0.1813600,0.0081941,-0.9260055,-0.3112617,-0.0760299,-0.0830109;...
0,0,0,0,0,0,0;...
0,-0.0424746,0.0617596,0.0739607,0.0881793,-0.8964447,-0.4213346;...
0,0,0,0,0,0,0;...
0,0,0,0,0,0,0;...
0,0,0,0,0,0,0;...
0,0,0,0,0,0,0;...
0,-0.3970222,-0.2780387,-0.1320049,0.1183719,-0.1097386,0.2343533;...
-0.5773503,0,0,0,0,0,0];

Actually, A has a precise physical meaning, and according to it I know
that another basis of its null space exists in the form
C = [C11, C12, 0; 0, C22, C23], where C11 is 7x2, C12 is 7x2,
C22 is 11x2 and C23 is 11x3:

C = [0, 0, 0, 0.5773503, 0, 0, 0;...
0, 0, -0.4616615, 0, 0, 0, 0;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0, 0.5773503, 0, 0, 0;...
0, 0, -0.4616615, 0, 0, 0, 0;...
1, 0, -0.4883661, 0, 0, 0, 0;...
0, 1, 0.3355536, 0, 0, 0, 0;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, -0.0199593, 0, 0.3118486, -0.9413430, -0.1289331;...
0, 0, 0.0954459, 0, -0.9463925, -0.3197754, 0.0456604;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0.0004000, 0, 0.0842117, -0.1077822, 0.9906015;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0, 0, 0, 0, 0;...
0, 0, 0.4616615, 0, 0, 0, 0;...
0, 0, 0, 0.5773503, 0, 0, 0];

Is your algorithm able to return C = [C11, C12, 0; 0, C22, C23], given
B = [B1; B2] and p, q, and r?

As I've said above, I've tried to play a lot with rref and lu
factorization, but the best result I've got is

D = [D11, 0; D21, D22], where D22 is 11x3 but is different from C23, and
the remaining columns cannot reduced by rref().

>
> Create a random 7x16 matrix.
>
> mat = RandomReal[{-10, 10}, {7, 16}];
>
> Find, and row reduce, the null space.
>
> nulls = NullSpace[mat];
> rednulls = RowReduce[nulls];
>
> We'll use p=4 and q=3.
>
> p = 4;
> q = Length[nulls] - p;
>
> The bottom part, your [0,C22,C23] section, is easy.
>
> bottom = Drop[rednulls, p];
>
> We'll use the rest as our top part, and make alterations to get zeros
> at the right end.
>
> top = Take[rednulls, p];
>
> From the description, you perhaps got this far. To do the rest, first
> reverse the null vectors in 'bottom', row reduce, and reverse back. We
> get a set of null vectors that is in echelon form columnwise from
> right-to-left.
>
> bottom2 = Map[Reverse, RowReduce[Map[Reverse, bottom]]];
>
> Use this to zero the 'top' null vectors on the right side.
>
> Do[top[[j]] = top[[j]] - top[[j, -k]]*bottom2[[k]], {j,
> Length[top]}, {k, Length[bottom2]}]
>
> Here is the result in this example. Notice 'top' is now zerod on the
> right.
>
> In[116]:= top
>
> Out[116]= {{1., 0., 0., 0., -0.1570521698815333, -0.1438145481730163,
> 0.3341102247948281, 1.159540140238518, 0.2594884364079637,
> 0.3116479687035286, -0.3244619655034073, 0., 0., 0., 0., 0.}, {0.,
> 1., 0., 0., -0.353199257121722, 0.3955447462849144,
> 0.2770180465857701, 1.051468466698785, 0.1646042200361716,
> 1.289988509255458, -0.314174133729317, 0., 0., 0., 0., 0.}, {0., 0.,
> 1., 0., 0.01528706008350322, -0.4786839021436973, \
> -0.6380269892684085, 1.108257764338746, 0.4819835401333382,
> 0.4796243014367019, -1.087136217299042, 0., 0., 0., 0., 0.}, {0.,
> 0., 0., 1., 0.1905092618416806, 0.5196853394491601,
> 0.756397394849917, -0.7050950551954204, -0.871705286441594, \
> -0.9738372685877903, 0.8759900364217903, 0., 0., 0., 0., 0.}}
>
> In[117]:= bottom
>
> Out[117]= {{0, 0, 0, 0, 1, 0., 0., 0., 0., -0.5597664757073788,
> 0.8143070871866038, 0.4277776146150173, -1.098944133145463,
> 0.8081363401427031, -2.848613830703109, 1.872743300071011}, {0, 0,
> 0, 0, 0, 1, 0., 0.,
> 0., -0.4570234191081754, -0.1822057163418105, -1.020755390589715, \
> -1.275200915927704, 0.4217003016771535, -0.3216906116940924,
> 1.137607237636676}, {0, 0, 0, 0, 0, 0, 1, 0.,
> 0., -2.057131526158108, 1.762612098425479,
> 1.519296054797632, -1.391652167046286,
> 0.3584888909059545, -3.946993942305765, 2.065619477936373}, {0, 0,
> 0, 0, 0, 0, 0, 1, 0., -0.2846507307315486, 0.2895074106852998,
> 0.4478459988247586, -1.530445195016555,
> 1.163129348653568, -2.008261891031013, 1.445298232599805}, {0, 0, 0,
> 0, 0, 0, 0, 0, 1,
> 0.7013048464911343, -1.428978238780057, -1.569680138947566,
> 0.4155594211966983, -1.988702096113409,
> 0.9380405673096524, -1.404713184245211}}
>
> We can check correctness by showing that the top and bottom are all
> null vectors, and combine to have rank 9, the rank of the original
> null space.
>
> In[120]:= nullset = Join[top, bottom];
>
> In[121]:= Max[Abs[mat.Transpose[nullset]]]
>
> Out[121]= 1.332267629550188*10^-14
>
> In[122]:= MatrixRank[nullset]
>
> Out[122]= 9
>
> Daniel Lichtblau
> Wolfram Research

Subject: rref, lu and matrix arrangements

From: Serge Steer

Date: 24 May, 2011 15:50:25

Message: 4 of 9

I think the following Scilab code solves your problem
it is based on the rowcomp function


p = 7; q = 11; r = 7;
B1=B(1:p,:);
B2=B(p+1:$,:);

[X1,r1]=colcomp(B1);X1=X1(:,$:-1:1)
T=B*X1;
//T as the following structure
//[T11 0
// T21 T22]
//where T11 has r1 columns
T21=T(p+1:$,1:r1);
[X2,r2]=colcomp(T21);
W=T21*X2;
//W as the following structure
//[0 W12]
//where W12 has r2 columns

//form the complete basis change matrix
X=X1*[X2 zeros(r1,r-r1);zeros(r-r1,r1) eye(r-r1,r-r1)]
C=B*X;clean(C)//clean used to set to zeros the very small elements and
so make the structure clear
t=r1-r2;
v=r-r1;
u=r-r2;
C11=C(1:p,1:t);
C12=C(1:p,t+1:$-v);
C13=C(1:p,$-v+1:$);
C21=C(p+1:$,1:t);
C22=C(p+1:$,t+1:$-v);
C23=C(p+1:$,$-v+1:$);





Le 24/05/2011 10:04, matt a écrit :
> On 05/23/2011 12:25 AM, Daniel Lichtblau wrote:
>> On May 22, 6:19 am, matt<n...@none.com> wrote:
>>> Dear all,
>>>
>>> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
>>> where B1 is pxr and B2 is qxr.
>>>
>>> Now, consider the case in which another basis of null(A) exists that can
>>> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
>>> C12 is pxu, C22 is qxu and C23 is qxv.
>>>
>>> Is there any algorithm which, when possible, returns
>>> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>>>
>>> I've tried to implement an algorithm which relies on rref and lu
>>> factorization, but I have some test cases in which it doesn't work.
>>>
>>> Is it reasonable to expect to solve this problem? Can you provide some
>>> suggestions?
>>>
>>> Thanks in advance
>>>
>>> --
>>> Matteo
>>
>> Will depend on dimensions. Your t should be perhaps p, or at least not
>> larger, for example.
>>
>> This might be along the lines you seek. I'll show an example with
>> Mathematica but
>> the code should translate readily to Matlab or other languages.
>
> Dear Daniel,
>
> first of all, thanks for time you took to reply.
>
> Unfortunately, I'm not familiar with Mathematica and I may have missed
> some crucial piece of your algorithm, but at first (also 2nd and 3rd)
> glance, it looks like the approach I've used too.
>
> I have a test case where my approach fails. I'd greatly appreciate if
> you could do the test with your algorithm; in case you managed it to
> work, I'll further investigate your approach to discover the differences
> with mine.
>
> Thanks in advance,
>
> Matteo.
>
> ========================================================================
> TEST CASE
> =========
>
> Let A be the following 16x18 matrix:
>
> A =
> [0.15005,-0.4318,-0.4318,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.4318,-0.15005;...
> -0.0479,0,0,0,0,0,0,-0.5,0,0,0,0,0,-1,0,0.4318,0,0.0479;...
> 0,-0.0479,-0.4797,0,0,0,0,0,0,0,0,0,0,0,-1,0.15005,-0.0479,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
> -0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.0682;...
> 0,-0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,-0.0682,0;...
> 0,0,0,0.15005,0,0,0,0,0,0,0,0,-1,0,0,0,0,-0.15005;...
> 0,0,0,0.2521,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.2521;...
> 0,0,0,0,0.2521,0,0,0,0,0,-0.1797,0,0,0,-1,0.15005,0.2521,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
> 0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.2682;...
> 0,0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,-0.2682,0;...
> -0.8660254,0.5,0.5,0,0,0,0,-0.8660254,0,0,0,0,0,0,0,0,0.5,0.8660254;...
> -0.5877853,0.8090170,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.8090170,0.5877853;...
> 0,0,0,0.5,-0.8660254,0,0,0,0,0,-0.8660254,0,0,0,0,0,-0.8660254,-0.5;...
> 0,0,0,0.8660254,0.5,0,0,0,0,0,0,0,0,0,0,0,0.5,-0.8660254];
>
> and let B = [B1;B2] the following 18x7 matrix (p = 7, q = 11, r = 7), a
> basis of A's kernel:
>
> B = [-0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
> 0,0,0,0,0,0,0;...
> -0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
> 0,-0.4674929,-0.1645678,-0.0222354,-0.0918726,0.3672059,-0.7814043;...
> 0,0.4589534,-0.5071254,-0.1336586,0.6822599,0.0935152,-0.2002428;...
> 0,0,0,0,0,0,0;...
> 0,-0.2514693,0.6927794,-0.2576987,0.6159429,0.1043717,-0.0114939;...
> 0,0.1813600,0.0081941,-0.9260055,-0.3112617,-0.0760299,-0.0830109;...
> 0,0,0,0,0,0,0;...
> 0,-0.0424746,0.0617596,0.0739607,0.0881793,-0.8964447,-0.4213346;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,-0.3970222,-0.2780387,-0.1320049,0.1183719,-0.1097386,0.2343533;...
> -0.5773503,0,0,0,0,0,0];
>
> Actually, A has a precise physical meaning, and according to it I know
> that another basis of its null space exists in the form
> C = [C11, C12, 0; 0, C22, C23], where C11 is 7x2, C12 is 7x2,
> C22 is 11x2 and C23 is 11x3:
>
> C = [0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, -0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, -0.4616615, 0, 0, 0, 0;...
> 1, 0, -0.4883661, 0, 0, 0, 0;...
> 0, 1, 0.3355536, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, -0.0199593, 0, 0.3118486, -0.9413430, -0.1289331;...
> 0, 0, 0.0954459, 0, -0.9463925, -0.3197754, 0.0456604;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.0004000, 0, 0.0842117, -0.1077822, 0.9906015;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0];
>
> Is your algorithm able to return C = [C11, C12, 0; 0, C22, C23], given
> B = [B1; B2] and p, q, and r?
>
> As I've said above, I've tried to play a lot with rref and lu
> factorization, but the best result I've got is
>
> D = [D11, 0; D21, D22], where D22 is 11x3 but is different from C23, and
> the remaining columns cannot reduced by rref().
>
>>
>> Create a random 7x16 matrix.
>>
>> mat = RandomReal[{-10, 10}, {7, 16}];
>>
>> Find, and row reduce, the null space.
>>
>> nulls = NullSpace[mat];
>> rednulls = RowReduce[nulls];
>>
>> We'll use p=4 and q=3.
>>
>> p = 4;
>> q = Length[nulls] - p;
>>
>> The bottom part, your [0,C22,C23] section, is easy.
>>
>> bottom = Drop[rednulls, p];
>>
>> We'll use the rest as our top part, and make alterations to get zeros
>> at the right end.
>>
>> top = Take[rednulls, p];
>>
>> From the description, you perhaps got this far. To do the rest, first
>> reverse the null vectors in 'bottom', row reduce, and reverse back. We
>> get a set of null vectors that is in echelon form columnwise from
>> right-to-left.
>>
>> bottom2 = Map[Reverse, RowReduce[Map[Reverse, bottom]]];
>>
>> Use this to zero the 'top' null vectors on the right side.
>>
>> Do[top[[j]] = top[[j]] - top[[j, -k]]*bottom2[[k]], {j,
>> Length[top]}, {k, Length[bottom2]}]
>>
>> Here is the result in this example. Notice 'top' is now zerod on the
>> right.
>>
>> In[116]:= top
>>
>> Out[116]= {{1., 0., 0., 0., -0.1570521698815333, -0.1438145481730163,
>> 0.3341102247948281, 1.159540140238518, 0.2594884364079637,
>> 0.3116479687035286, -0.3244619655034073, 0., 0., 0., 0., 0.}, {0.,
>> 1., 0., 0., -0.353199257121722, 0.3955447462849144,
>> 0.2770180465857701, 1.051468466698785, 0.1646042200361716,
>> 1.289988509255458, -0.314174133729317, 0., 0., 0., 0., 0.}, {0., 0.,
>> 1., 0., 0.01528706008350322, -0.4786839021436973, \
>> -0.6380269892684085, 1.108257764338746, 0.4819835401333382,
>> 0.4796243014367019, -1.087136217299042, 0., 0., 0., 0., 0.}, {0.,
>> 0., 0., 1., 0.1905092618416806, 0.5196853394491601,
>> 0.756397394849917, -0.7050950551954204, -0.871705286441594, \
>> -0.9738372685877903, 0.8759900364217903, 0., 0., 0., 0., 0.}}
>>
>> In[117]:= bottom
>>
>> Out[117]= {{0, 0, 0, 0, 1, 0., 0., 0., 0., -0.5597664757073788,
>> 0.8143070871866038, 0.4277776146150173, -1.098944133145463,
>> 0.8081363401427031, -2.848613830703109, 1.872743300071011}, {0, 0,
>> 0, 0, 0, 1, 0., 0.,
>> 0., -0.4570234191081754, -0.1822057163418105, -1.020755390589715, \
>> -1.275200915927704, 0.4217003016771535, -0.3216906116940924,
>> 1.137607237636676}, {0, 0, 0, 0, 0, 0, 1, 0.,
>> 0., -2.057131526158108, 1.762612098425479,
>> 1.519296054797632, -1.391652167046286,
>> 0.3584888909059545, -3.946993942305765, 2.065619477936373}, {0, 0,
>> 0, 0, 0, 0, 0, 1, 0., -0.2846507307315486, 0.2895074106852998,
>> 0.4478459988247586, -1.530445195016555,
>> 1.163129348653568, -2.008261891031013, 1.445298232599805}, {0, 0, 0,
>> 0, 0, 0, 0, 0, 1,
>> 0.7013048464911343, -1.428978238780057, -1.569680138947566,
>> 0.4155594211966983, -1.988702096113409,
>> 0.9380405673096524, -1.404713184245211}}
>>
>> We can check correctness by showing that the top and bottom are all
>> null vectors, and combine to have rank 9, the rank of the original
>> null space.
>>
>> In[120]:= nullset = Join[top, bottom];
>>
>> In[121]:= Max[Abs[mat.Transpose[nullset]]]
>>
>> Out[121]= 1.332267629550188*10^-14
>>
>> In[122]:= MatrixRank[nullset]
>>
>> Out[122]= 9
>>
>> Daniel Lichtblau
>> Wolfram Research
>

Subject: rref, lu and matrix arrangements

From: Daniel Lichtblau

Date: 24 May, 2011 16:31:58

Message: 5 of 9

On May 24, 3:04 am, matt <n...@none.com> wrote:
> On 05/23/2011 12:25 AM, Daniel Lichtblau wrote:
>
>
>
>
>
>
>
>
>
> > On May 22, 6:19 am, matt<n...@none.com>  wrote:
> >> Dear all,
>
> >> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
> >> where B1 is pxr and B2 is qxr.
>
> >> Now, consider the case in which another basis of null(A) exists that can
> >> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
> >> C12 is pxu, C22 is qxu and C23 is qxv.
>
> >> Is there any algorithm which, when possible, returns
> >> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>
> >> I've tried to implement an algorithm which relies on rref and lu
> >> factorization, but I have some test cases in which it doesn't work.
>
> >> Is it reasonable to expect to solve this problem? Can you provide some
> >> suggestions?
>
> >> Thanks in advance
>
> >> --
> >> Matteo
>
> > Will depend on dimensions. Your t should be perhaps p, or at least not
> > larger, for example.
>
> > This might be along the lines you seek. I'll show an example with
> > Mathematica but
> > the code should translate readily to Matlab or other languages.
>
> Dear Daniel,
>
> first of all, thanks for time you took to reply.
>
> Unfortunately, I'm not familiar with Mathematica and I may have missed
> some crucial piece of your algorithm, but at first (also 2nd and 3rd)
> glance, it looks like the approach I've used too.
>
> I have a test case where my approach fails. I'd greatly appreciate if
> you could do the test with your algorithm; in case you managed it to
> work, I'll further investigate your approach to discover the differences
> with mine.
>
> Thanks in advance,
>
> Matteo.
>
> ========================================================================
> TEST CASE
> =========
>
> Let A be the following 16x18 matrix:
>
> A = [0.15005,-0.4318,-0.4318,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.4318,-0.15005;...
> -0.0479,0,0,0,0,0,0,-0.5,0,0,0,0,0,-1,0,0.4318,0,0.0479;...
> 0,-0.0479,-0.4797,0,0,0,0,0,0,0,0,0,0,0,-1,0.15005,-0.0479,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
> -0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.0682;...
> 0,-0.0682,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,-0.0682,0;...
> 0,0,0,0.15005,0,0,0,0,0,0,0,0,-1,0,0,0,0,-0.15005;...
> 0,0,0,0.2521,0,0,0,0,0,0,0,0,0,-1,0,0,0,-0.2521;...
> 0,0,0,0,0.2521,0,0,0,0,0,-0.1797,0,0,0,-1,0.15005,0.2521,0;...
> 0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0;...
> 0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,0,0,0.2682;...
> 0,0,0,0,-0.2682,0,0,0,0,0,0,0,0,0,-1,0,-0.2682,0;...
> -0.8660254,0.5,0.5,0,0,0,0,-0.8660254,0,0,0,0,0,0,0,0,0.5,0.8660254;...
> -0.5877853,0.8090170,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.8090170,0.5877853;...
> 0,0,0,0.5,-0.8660254,0,0,0,0,0,-0.8660254,0,0,0,0,0,-0.8660254,-0.5;...
> 0,0,0,0.8660254,0.5,0,0,0,0,0,0,0,0,0,0,0,0.5,-0.8660254];
>
> and let B = [B1;B2] the following 18x7 matrix (p = 7, q = 11, r = 7), a
> basis of A's kernel:
>
> B = [-0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
> 0,0,0,0,0,0,0;...
> -0.5773503,0,0,0,0,0,0;...
> 0,0.3970222,0.2780387,0.1320049,-0.1183719,0.1097386,-0.2343533;...
> 0,-0.4674929,-0.1645678,-0.0222354,-0.0918726,0.3672059,-0.7814043;...
> 0,0.4589534,-0.5071254,-0.1336586,0.6822599,0.0935152,-0.2002428;...
> 0,0,0,0,0,0,0;...
> 0,-0.2514693,0.6927794,-0.2576987,0.6159429,0.1043717,-0.0114939;...
> 0,0.1813600,0.0081941,-0.9260055,-0.3112617,-0.0760299,-0.0830109;...
> 0,0,0,0,0,0,0;...
> 0,-0.0424746,0.0617596,0.0739607,0.0881793,-0.8964447,-0.4213346;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,0,0,0,0,0,0;...
> 0,-0.3970222,-0.2780387,-0.1320049,0.1183719,-0.1097386,0.2343533;...
> -0.5773503,0,0,0,0,0,0];
>
> Actually, A has a precise physical meaning, and according to it I know
> that another basis of its null space exists in the form
> C = [C11, C12, 0; 0, C22, C23], where C11 is 7x2, C12 is 7x2,
> C22 is 11x2 and C23 is 11x3:
>
> C = [0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, -0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0;...
> 0, 0, -0.4616615, 0, 0, 0, 0;...
> 1, 0, -0.4883661, 0, 0, 0, 0;...
> 0, 1, 0.3355536, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, -0.0199593, 0, 0.3118486, -0.9413430, -0.1289331;...
> 0, 0, 0.0954459, 0, -0.9463925, -0.3197754, 0.0456604;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.0004000, 0, 0.0842117, -0.1077822, 0.9906015;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0, 0, 0, 0, 0;...
> 0, 0, 0.4616615, 0, 0, 0, 0;...
> 0, 0, 0, 0.5773503, 0, 0, 0];
>
> Is your algorithm able to return C = [C11, C12, 0; 0, C22, C23], given
> B = [B1; B2] and p, q, and r?
>
> As I've said above, I've tried to play a lot with rref and lu
> factorization, but the best result I've got is
>
> D = [D11, 0; D21, D22], where D22 is 11x3 but is different from C23, and
> the remaining columns cannot reduced by rref().
>
>
>
>
>
>
>
>
>
> > Create a random 7x16 matrix.
>
> > mat = RandomReal[{-10, 10}, {7, 16}];
>
> > Find, and row reduce, the null space.
>
> > nulls = NullSpace[mat];
> > rednulls = RowReduce[nulls];
>
> > We'll use p=4 and q=3.
>
> > p = 4;
> > q = Length[nulls] - p;
>
> > The bottom part, your [0,C22,C23] section, is easy.
>
> > bottom = Drop[rednulls, p];
>
> > We'll use the rest as our top part, and make alterations to get zeros
> > at the right end.
>
> > top = Take[rednulls, p];
>
> >  From the description, you perhaps got this far. To do the rest, first
> > reverse the null vectors in 'bottom', row reduce, and reverse back. We
> > get a set of null vectors that is in echelon form columnwise from
> > right-to-left.
>
> > bottom2 = Map[Reverse, RowReduce[Map[Reverse, bottom]]];
>
> > Use this to zero the 'top' null vectors on the right side.
>
> > Do[top[[j]] = top[[j]] - top[[j, -k]]*bottom2[[k]], {j,
> >    Length[top]}, {k, Length[bottom2]}]
>
> > Here is the result in this example. Notice 'top' is now zerod on the
> > right.
>
> > In[116]:= top
>
> > Out[116]= {{1., 0., 0., 0., -0.1570521698815333, -0.1438145481730163,
> >    0.3341102247948281, 1.159540140238518, 0.2594884364079637,
> >    0.3116479687035286, -0.3244619655034073, 0., 0., 0., 0., 0.}, {0.,
> >    1., 0., 0., -0.353199257121722, 0.3955447462849144,
> >    0.2770180465857701, 1.051468466698785, 0.1646042200361716,
> >    1.289988509255458, -0.314174133729317, 0., 0., 0., 0., 0.}, {0., 0.,
> >     1., 0., 0.01528706008350322, -0.4786839021436973, \
> > -0.6380269892684085, 1.108257764338746, 0.4819835401333382,
> >    0.4796243014367019, -1.087136217299042, 0., 0., 0., 0., 0.}, {0.,
> >    0., 0., 1., 0.1905092618416806, 0.5196853394491601,
> >    0.756397394849917, -0.7050950551954204, -0.871705286441594, \
> > -0.9738372685877903, 0.8759900364217903, 0., 0., 0., 0., 0.}}
>
> > In[117]:= bottom
>
> > Out[117]= {{0, 0, 0, 0, 1, 0., 0., 0., 0., -0.5597664757073788,
> >    0.8143070871866038, 0.4277776146150173, -1.098944133145463,
> >    0.8081363401427031, -2.848613830703109, 1.872743300071011}, {0, 0,
> >    0, 0, 0, 1, 0., 0.,
> >    0., -0.4570234191081754, -0.1822057163418105, -1.020755390589715, \
> > -1.275200915927704, 0.4217003016771535, -0.3216906116940924,
> >    1.137607237636676}, {0, 0, 0, 0, 0, 0, 1, 0.,
> >    0., -2.057131526158108, 1.762612098425479,
> >    1.519296054797632, -1.391652167046286,
> >    0.3584888909059545, -3.946993942305765, 2.065619477936373}, {0, 0,
> >    0, 0, 0, 0, 0, 1, 0., -0.2846507307315486, 0.2895074106852998,
> >    0.4478459988247586, -1.530445195016555,
> >    1.163129348653568, -2.008261891031013, 1.445298232599805}, {0, 0, 0,
> >     0, 0, 0, 0, 0, 1,
> >    0.7013048464911343, -1.428978238780057, -1.569680138947566,
> >    0.4155594211966983, -1.988702096113409,
> >    0.9380405673096524, -1.404713184245211}}
>
> > We can check correctness by showing that the top and bottom are all
> > null vectors, and combine to have rank 9, the rank of the original
> > null space.
>
> > In[120]:= nullset = Join[top, bottom];
>
> > In[121]:= Max[Abs[mat.Transpose[nullset]]]
>
> > Out[121]= 1.332267629550188*10^-14
>
> > In[122]:= MatrixRank[nullset]
>
> > Out[122]= 9
>
> > Daniel Lichtblau
> > Wolfram Research

I cannot replicate exactly the matrix you have in mind. Also I do not
have a clear idea of how the sizes work. But I can show something that
might be along the right lines for this particular matrix. First I'll
mention that I had misunderstood what is to be zeroed. So this new
code is slightly different from before.

I define 'mat' to be your matrix 'A' above, though in Mathematica
format.

mat = {{0.15005, -0.4318, -0.4318, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0,
    0, 0, -0.4318, -0.15005}, {-0.0479, 0, 0, 0, 0, 0, 0, -0.5, 0, 0,
    0, 0, 0, -1, 0, 0.4318, 0, 0.0479}, {0, -0.0479, -0.4797, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, -1, 0.15005, -0.0479, 0}, {0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0}, {-0.0682, 0, 0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0.0682}, {0, -0.0682, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -0.0682, 0}, {0, 0, 0, 0.15005,
    0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -0.15005}, {0, 0, 0,
    0.2521, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, -0.2521}, {0, 0,
    0, 0, 0.2521, 0, 0, 0, 0, 0, -0.1797, 0, 0, 0, -1, 0.15005,
    0.2521, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0,
    0}, {0, 0, 0, -0.2682, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0,
    0.2682}, {0, 0, 0, 0, -0.2682, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1,
    0, -0.2682, 0}, {-0.8660254, 0.5, 0.5, 0, 0, 0, 0, -0.8660254, 0,
    0, 0, 0, 0, 0, 0, 0, 0.5, 0.8660254}, {-0.5877853, 0.8090170, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.8090170, 0.5877853}, {0,
    0, 0, 0.5, -0.8660254, 0, 0, 0, 0, 0, -0.8660254, 0, 0, 0, 0,
    0, -0.8660254, -0.5}, {0, 0, 0, 0.8660254, 0.5, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0.5, -0.8660254}};

I will use Chop[] to remove small non-zero values. This is purely a
cosmetic touch.

nulls = NullSpace[mat];
rednulls = Chop[Map[Reverse, RowReduce[Map[Reverse, nulls]]]]

{{1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
 {0, -1., 0, 0, -1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}

Mathematica gives the nulls as a list, that is to say, each row is a
null vector. You want the matrix which means switching, eventually, to
column form. But not until we do needed operations. I see that the
first two columns should have all zeros in the last 11 positions. So
I'll use the last two row reduced nulls for those, since they are the
ones with the most zeros at the end. (Why? Because I had reversed
nulls before row reducing, then reversed back.)

In[51]:= k = 2;
first = Take[rednulls, -k]
last = Drop[rednulls, -k]

Out[52]= {{0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0,
  0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}

Out[53]= {{1., 0, 0, 1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1}, {0, -1., 0, 0, -1., 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}, {0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1,
  0, 0, 0, 0, 0, 0, 0, 0, 0}}

For the remaining five nulls we want some zeros at the end of three of
them (or as many as can be managed, I guess). That can be done with
the same reverse-reduce-reverse cycle.

In[49]:= last2 = Map[Reverse, RowReduce[Map[Reverse, last]]]

Out[49]= {
  {1., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
1},
  {0., -1., 0., 0., -1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.,
1, 0},
  {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1, 0, 0, 0, 0, 0, 0},
  {0., 0., 0., 0., 0., 0., 0., 0., 0., 1, 0, 0, 0, 0, 0, 0, 0, 0},
  {0., 0., 0., 0., 0., 0., 0., 0., 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}}

Now form the matrix of transpose null vectors.

In[54]:= nullmat = Transpose[Join[first, last]]

Out[54]= {
 {0, 0, 1., 0, 0, 0, 0},
 {0, 0, 0, -1., 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 1., 0, 0, 0, 0},
 {0, 0, 0, -1., 0, 0, 0},
 {0, 1, 0, 0, 0, 0, 0},
 {1, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 1},
 {0, 0, 0, 0, 0, 1, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 1, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 0, 0, 0, 0},
 {0, 0, 0, 1, 0, 0, 0},
 {0, 0, 1, 0, 0, 0, 0}}

I think this has at least the correct zero sub-matrices.

Quick confirmation that it is a reasonable null matrix for 'mat'.

In[55]:= Max[Abs[mat.nullmat]]

Out[55]= 4.44089*10^-16

I hope this gets you a bit closer.

Daniel Lichtblau
Wolfram Research

Subject: rref, lu and matrix arrangements

From: Ray Koopman

Date: 25 May, 2011 07:31:11

Message: 6 of 9

On May 22, 4:19 am, matt <n...@none.com> wrote:
> Dear all,
>
> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
> where B1 is pxr and B2 is qxr.
>
> Now, consider the case in which another basis of null(A) exists that
> can be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
> C12 is pxu, C22 is qxu and C23 is qxv.
>
> Is there any algorithm which, when possible, returns
> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>
> I've tried to implement an algorithm which relies on rref and lu
> factorization, but I have some test cases in which it doesn't work.
>
> Is it reasonable to expect to solve this problem? Can you provide some
> suggestions?
>
> Thanks in advance
>
> --
> Matteo

It seems pretty straightforward once you
look at the partitioned matrix equation.

[B1] [T1 T2 T3] = [C11 C12 0 ]
[B2] [ 0 C22 C23]

In Mathematica syntax,

T1 = PseudoInverse[B1] . C11
T2 = PseudoInverse[Join[B1,B2]] . Join[C12,C22]
T3 = PseudoInverse[B2] . C23

Have I missed something?

Subject: rref, lu and matrix arrangements

From: Ray Koopman

Date: 25 May, 2011 07:44:15

Message: 7 of 9

On May 25, 12:31 am, Ray Koopman <koop...@sfu.ca> wrote:
> On May 22, 4:19 am, matt <n...@none.com> wrote:
>> Dear all,
>>
>> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
>> where B1 is pxr and B2 is qxr.
>>
>> Now, consider the case in which another basis of null(A) exists that
>> can be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
>> C12 is pxu, C22 is qxu and C23 is qxv.
>>
>> Is there any algorithm which, when possible, returns
>> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>>
>> I've tried to implement an algorithm which relies on rref and lu
>> factorization, but I have some test cases in which it doesn't work.
>>
>> Is it reasonable to expect to solve this problem? Can you provide some
>> suggestions?
>>
>> Thanks in advance
>>
>> --
>> Matteo
>
> It seems pretty straightforward once you
> look at the partitioned matrix equation.
>
> [B1] [T1 T2 T3] = [C11 C12 0 ]
> [B2] [ 0 C22 C23]
>
> In Mathematica syntax,
>
> T1 = PseudoInverse[B1] . C11
> T2 = PseudoInverse[Join[B1,B2]] . Join[C12,C22]
> T3 = PseudoInverse[B2] . C23
>
> Have I missed something?

Or even simpler, T = PseudoInverse[B] . C

Subject: rref, lu and matrix arrangements

From: Rune Allnor

Date: 25 May, 2011 08:47:46

Message: 8 of 9

On May 22, 1:19 pm, matt <n...@none.com> wrote:
> Dear all,
>
> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
> where B1 is pxr and B2 is qxr.
>
> Now, consider the case in which another basis of null(A) exists that can
> be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
> C12 is pxu, C22 is qxu and C23 is qxv.
>
> Is there any algorithm which, when possible, returns
> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?

So you have two bases B and C of the subspace null(A),
and want to find the transform T between B and C?

C = TB

I'd have a look at the chapter on 'intersection of subspaces'
in 'Matrix Computations' by Golub & van Loan.

Rune

Subject: rref, lu and matrix arrangements

From: Ray Koopman

Date: 26 May, 2011 22:33:17

Message: 9 of 9

On May 25, 12:31 am, Ray Koopman <koop...@sfu.ca> wrote:
> On May 22, 4:19 am, matt <n...@none.com> wrote:
>> Dear all,
>>
>> let A be an mxn matrix, and let B = [B1; B2] a basis nxr of null(A),
>> where B1 is pxr and B2 is qxr.
>>
>> Now, consider the case in which another basis of null(A) exists that
>> can be written as C = [C11, C12, 0; 0, C22, C23], where C11 is pxt,
>> C12 is pxu, C22 is qxu and C23 is qxv.
>>
>> Is there any algorithm which, when possible, returns
>> [C11, C12, 0; 0, C22, C23] given [B1;B2] and their sizes p, q, and r?
>>
>> I've tried to implement an algorithm which relies on rref and lu
>> factorization, but I have some test cases in which it doesn't work.
>>
>> Is it reasonable to expect to solve this problem? Can you provide some
>> suggestions?
>>
>> Thanks in advance
>>
>> --
>> Matteo
>
> It seems pretty straightforward once you
> look at the partitioned matrix equation.
>
> [B1] [T1 T2 T3] = [C11 C12 0 ]
> [B2] [ 0 C22 C23]
>
> In Mathematica syntax,
>
> T1 = PseudoInverse[B1] . C11
> T2 = PseudoInverse[Join[B1,B2]] . Join[C12,C22]
> T3 = PseudoInverse[B2] . C23
>
> Have I missed something?

Apparently. In a private email, Dan Lichtblau wrote "He does not know
C in general. So the goal is to find C, not the transformation matrix
T."

So I reinterpreted the original question as "Is there any algorithm
which, when possible, returns [C11, C12, 0; 0, C22, C23], given
[B1;B2] and their sizes p, q, and r, where only the blocks of zeros
in C are specified, and the other blocks are free?"

The answer is Yes, but the result is far from unique. T1 can be any
matrix whose columns are a basis for the null space of the rows of B2.
Similarly, T3 can be any matrix whose columns are a basis for the null
space of the rows of B1. T2 is even less constrained, in that it need
only maintain T at full rank.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us