How to Prove Certain Matrix Operations and Understand Their Properties?

[akerman]

1. So firstly I would like to show that product of the matrices L21,L31,... in the derivation of the LU decmoposition is lower triangular. I have already shown that product of upper and lower triandular matices is upper or lower. Now I don't know how to show the derivation.

2. I have been given I - ab^T which are member or reals ^n*n. I is identity and a,b are vectors. I need to show what conditions on a and b does the inverse have the form I + ab^T ? Can anyone help me with this as well?

3. I have been given that A=uv^T and both u and v are vectors. I need to find out number of floating point operations required to compute (uv^T)x and how many operations are needed for u(v^Tx). I know that operation on uv^T is outer product of u and v but how do I show the number of floating points?

Thanks

 

[Opalg]

Re: matrix operations proofs

1. So firstly I would like to show that product of the matrices L21,L31,... in the derivation of the LU decmoposition is lower triangular. I have already shown that product of upper and lower triandular matices is upper or lower. Now I don't know how to show the derivation.

2. I have been giver I - ab^T which are member or reals ^n*n. I is identity and a,b are vectors. I need to show what conditions on a and be does the inverse have the form I + ab^T ? Can anyone help me with this as well?

Thanks

Hint for 2.: $(I - ab^{\mathrm{\small T}})(I + ab^{\mathrm{\small T}}) = I - a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}}$.

 

[akerman]

Re: matrix operations proofs

Hint for 2.: $(I - ab^{\mathrm{\small T}})(I + ab^{\mathrm{\small T}}) = I - a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}}$.

but I still don't get how to show the conditions on a and be does and why the inverse have the form I + ab^T?

 

[Deveno]

Not sure if this is what Opalg was getting at, but note that $b^Ta$ is a scalar...

 

[I like Serena]

2. I have been given $I - ab^T$ which are member or reals ${}^{n \times n}$. I is identity and $a,b$ are vectors. I need to show what conditions on $a$ and $b$ does the inverse have the form $I + ab^T$ ? Can anyone help me with this as well?

but I still don't get how to show the conditions on a and be does and why the inverse have the form $I + ab^T$?

If $I - ab^T$ has an inverse of the form $I + ab^T$, then their product has to be the identity matrix $I$...

3. I have been given that $A=uv^T$ and both $u$ and $v$ are vectors. I need to find out number of floating point operations required to compute $(uv^T)x$ and how many operations are needed for $u(v^Tx)$. I know that operation on $u^{}v^T$ is outer product of $u$ and $v$ but how do I show the number of floating points?

Suppose $u=(u_1, u_2, u_3)$ and suppose $v=(v_1, v_2, v_3)$, what are the components of the matrix $u^{}v^T$?
How many multiplications will it take as a minimum to calculate all the elements (hint: it is less than $3 \times 3$)?

 

[akerman]

If $I - ab^T$ has an inverse of the form $I + ab^T$, then their product has to be the identity matrix $I$...

Suppose $u=(u_1, u_2, u_3)$ and suppose $v=(v_1, v_2, v_3)$, what are the components of the matrix $u^{}v^T$?
How many multiplications will it take as a minimum to calculate all the elements (hint: it is less than $3 \times 3$)?

For the second one I need to say what conditions a and b have to have. Does that mean given a proof of the rank? Or Can it be enough just to show the product of $I - ab^T$ and $I + ab^T$

Some more help?

For the third question is it good to show something such as the m×n matrix A has rank 1. Then any two rows of A are linearly dependent and that A must have some non-zero row. Let vt be a non-zero row of A so that v ∈ Rn. But I still don't get how to show the number of floating points?

 

[Deveno]

To calculate the "outer product" of 2 3-vectors you need 9 separate multiplications, that is all products $u_iv_j,\ i,j = 1,2,3$.

In your "inverse" question, what happens if $a,b$ are orthogonal?

For an actual calculation try $a = (1,1), b = (-1,1)$.

 

[akerman]

To calculate the "outer product" of 2 3-vectors you need 9 separate multiplications, that is all products $u_iv_j,\ i,j = 1,2,3$.

In your "inverse" question, what happens if $a,b$ are orthogonal?

For an actual calculation try $a = (1,1), b = (-1,1)$.

So for this one A=uv^T would it be ok to give this answer? View attachment 1998

But it only gives the floating operations for (uv^T) does it change if we have (uv^T)x ? In fact I need to show how many FLOPs are needed to compute (uvT)x and u(vTx) taking into account brakets... How does that change the calculation I have attached?

 

[Deveno]

Well, yes, any time you compute something else you're going to have more operations.

So now you have an mxm matrix times an mx1 vector. How many operations? Can you count them?

 

[akerman]

Well, yes, any time you compute something else you're going to have more operations.

So now you have an mxm matrix times an mx1 vector. How many operations? Can you count them?

So if we have MxM and Mx1 then will it be just M^3? But about the brackets does that add anything to the FLOPs?

What about the other one is it just (2M-1)* M ?

 

[Deveno]

To calculate the product of an mxm matrix with an mx1 vector, we need to do the following:

Take the inner product of each row of the matrix with the vector. We need to do this m times, so the total flops will be:

m*(whatever it takes to do an inner product of two m-vectors).

To take the inner product, we need to form m terms of a sum (the product of each row-entry by each entry of the m-vector (mx1 matrix)), and then sum them.(which will result in m-1 additional flops).

You do the math.

 

[akerman]

To calculate the product of an mxm matrix with an mx1 vector, we need to do the following:

Take the inner product of each row of the matrix with the vector. We need to do this m times, so the total flops will be:

m*(whatever it takes to do an inner product of two m-vectors).

To take the inner product, we need to form m terms of a sum (the product of each row-entry by each entry of the m-vector (mx1 matrix)), and then sum them.(which will result in m-1 additional flops).

You do the math.

So for (uv^T)x I found that for uv^T part we are doing M*M operations then we doing matrix times vector which gave me 2m^2-M. So now do I just add M*M + 2m^2-M? Which will result M^3-M is that correct?

I also got 2m-1 + m which is 3m-1 Flops for u(v^Tx) is this correct as well?

 

[I like Serena]

Hint for 2.: $(I - ab^{\mathrm{\small T}})(I + ab^{\mathrm{\small T}}) = I - a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}}$.

For the second one I need to say what conditions a and b have to have. Does that mean given a proof of the rank? Or Can it be enough just to show the product of $I - ab^T$ and $I + ab^T$

Some more help?

If $I + ab^T$ is the inverse of $I - ab^T$, then we must have:
$$I - a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}} = I$$

In other words, since $ (b^{\mathrm{\small T}}a)$ is a scalar:
$$a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}} = (b^{\mathrm{\small T}}a)ab^{\mathrm{\small T}} = 0$$
This will only be the case if either $b^{\mathrm{\small T}}a = 0$ or $ab^{\mathrm{\small T}} = \vec 0$. Or in other words, if their dot product is zero. This happens exactly when the vectors are perpendicular to each other, or if either of them is the zero vector.

So for (uv^T)x I found that for uv^T part we are doing M*M operations then we doing matrix times vector which gave me 2m^2-M. So now do I just add M*M + 2m^2-M? Which will result M^3-M is that correct?

$m \times m + 2m^2-m = 3m^2 - m$

As you can see, this is different from $m^3-m$.

I also got 2m-1 + m which is 3m-1 Flops for u(v^Tx) is this correct as well?

This is correct.
It would appear this is way cheaper to evaluate! ;)

 

[akerman]

If $I + ab^T$ is the inverse of $I - ab^T$, then we must have:
$$I - a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}} = I$$

In other words, since $ (b^{\mathrm{\small T}}a)$ is a scalar:
$$a(b^{\mathrm{\small T}}a)b^{\mathrm{\small T}} = (b^{\mathrm{\small T}}a)ab^{\mathrm{\small T}} = 0$$
This will only be the case if either $b^{\mathrm{\small T}}a = 0$ or $ab^{\mathrm{\small T}} = \vec 0$. Or in other words, if their dot product is zero. This happens exactly when the vectors are perpendicular to each other, or if either of them is the zero vector.

$m \times m + 2m^2-m = 3m^2 - m$

As you can see, this is different from $m^3-m$.
This is correct.
It would appear this is way cheaper to evaluate! ;)

Oh yes, thanks you I just added it incorrectly but rest of it is really useful and thanks again.