74 views (last 30 days)

Suppose I have a matrix C, dimension m x n, m < n, and that rank(C) = m.

I wish to find a marix V, dimension n-m x n, such that the square matrix T = [C ; V] is nonsingular.

What is a good criterion to use to select a V and how can one find that V that meets the crtierion, bearing in mind that T will be used for caculations like T\A*T?

For example, suppose

>> C = [1 2 3 4 5;5 6 7 8 9];

>> rank(C)

ans =

2

Then one possiblity is to define V by the null space of C

>> V1=null(C)'; T1 = [C;V1]; rank(T1)

ans =

5

Is this guaranteed to work for all C from a theoretical standpoint? If so, is this appoach too limiting insofar as there are solutions for V that don't live in the null space of C? Is there a possibiltiy of problem with null(C) if C is close to not being full rank?

For this simple example, another solution can be found by inspection:

>> V2 = [zeros(3,2) eye(3)];T2 = [C;V2]; rank(T2)

ans =

5

V2 has some appeal because it looks "simple" with only three non-zero elements that are all untiy. But can such a "simple" matrix be found when the C doesn't easily lend itself to inspection?

Neither solution looks all that appealing with respect to rcond

>> [rcond(T1) rcond(T2)]

ans =

3.2104e-02 8.3333e-03

though maybe these aren't all that bad.

In summary, are there any suggestions on how to find V?

David Goodmanson
on 1 Jan 2021

Edited: David Goodmanson
on 1 Jan 2021

Hi Paul,

First of all, if C is not close to full rank, there can be numerical problems with most any calculation involving C. Ignoring that, then every solution V does have to include all of null(C), and every V that does so will have rank n. note added> And M*null(C) where M is nonsingular is also a solution as Matt has mentioned.

But V does not have to fully " live in the null space of C ", in the sense that adding linear combinations of the rows of C to any of the rows of V still gives a solution.

The " simple " V2 approach does not work because without knowing C you can never be sure that some linear combination of the rows of V2 or (some similar matrix) does not reproduce one of the rows of C. In that case the rank of the full matrix will not be n.

C = [[1 2 3 4 5]

[5 6 7 8 9]];

V = null(C)'

A = [C; V];

cA = cond(A)

rcA = rcond(A)

cA = 17.5328

rcA = 0.0321

Your condition numbers are not that bad, but that has something to do with scaling. The average value of the rows of C are 3 and 8. The null space matrix V has the property that V'V = eye(n-m), so the values of V are less than 1.

C = [[1 2 3 4 5]

[5 6 7 8 9]];

V = 5*null(C)'

then

cA = 10.8681

rcA = 0.0474

which helps a little. As opposed to

C = [100*[1 2 3 4 5]

100*[5 6 7 8 9]];

V = null(C)'

then

cA = 1.7533e+03

rcA = 4.1414e-04

so you have to make sure that the size of C and the size of V are similar.

Bruno Luong
on 2 Jan 2021

But I did give the form of the solution

xd = smin + rand(p,1)*(smax-smin); % you could flip randomly the sign of xd if you want

M = diag(xd);

to obtain best possible COND(T). Why using FMINCON for such problem where a simple form has explicit formula?

Matt J
on 31 Dec 2020

Edited: Matt J
on 1 Jan 2021

V must be of the form A*C+B*null(C).' where B is a non-singular matrix.

I don't think the rconds in your example are bad at all, but you can improve them somewhat using row normalization:

>> rcond(normalize(T1,2,'norm'))

ans =

0.0516

>> rcond(normalize(T2,2,'norm'))

ans =

0.0219

Matt J
on 1 Jan 2021

Sorry, I meant that V must be of the form,

V=A*C+B*null(C).'

where B is a non-singular matrix. Because the row spaces of C and null(C).' are orthogonal complements, this is the only way that the rows of T will span all of , which is a requirement for non-singularity.

I can't normalize T1 that way, because that also changes the rows of C, which is not allowed.

Why not? Who is making the rules? If you can't, then you are stuck with whatever conditioning the rows of C limit you to.

Bruno Luong
on 1 Jan 2021

Edited: Bruno Luong
on 1 Jan 2021

C = [1 2 3 4 5;5 6 7 8 9];

[m,n] = size(C);

[Q,R] = qr(C.');

p=n-m;

X = rand(n,p);

% X(m+1:n+1:end) = X(m+1:n+1:end) + 0.5; % uncomment this to reenforce numerical rank

V = (Q*X).';

T = [C;V]

rank(T)

The important "criteria" here is X(m+k,k) ~= 0 for all k=1,...p; which is achieved by RAND() function, (rand never returns 0).

and this warranty det(T) > 0, therefore T is full rank.

To avoid "numerical" rank getting less than n, uncomment the commented line in the code, which make sure

X(m+k,k) >= 0.5

for all k=1,...p, (or whatever striclty positive value instead of 0.5).

Bruno Luong
on 1 Jan 2021

The condition of T is limited by the extrem singular values of C. C is given you cannot do anything to make it closer to 1, barely you can generate T that is not degrade it, like this:

[m,n] = size(C);

[Q,R] = qr(C.');

p=n-m;

s = abs(svd(C));

smin = min(s);

smax = max(s); % smax/smin is the limits of cond(T)

xd = smin + rand(p,1)*(smax-smin); % you could flip randomly the sign of xd if you want

X = [zeros(m,p); diag(xd)];

V = (Q*X).';

T = [C;V]

smax/smin

cond(T)

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 0 Comments

Sign in to comment.