Solving Equation (21) to (49): A Guide

[perplexabot]

Hey all. So I think I've been trying to figure this out longer than I should, that is why I am here now. I was reading an ieee paper and have been pondering a missing proof (the paper deems this proof too easy to show, literally... I must be really stupid or something). It is a simple question. How did they get from equation (21) to equation (49). I actually prefer hints rather than a definite answer, but of course anything is appreciated at this point.

Here is equation (21):

And here is equation (49), along with some verbiage:

I have tried many things with no avail. I have also tried working backwards, starting from (49), I did get nice equations, but nothing that has gotten me from (21) to (49). I can post this nice equation I speak of, but I doubt it would help.

If you are interested, here is a link to the paper I am reading.

Thank you for your time.

 

[jedishrfu]

Did you notice 28 where it has a matrix multiplication? Doesn't that expand into 49 after some work?

 

[perplexabot]

Did you notice 28 where it has a matrix multiplication? Doesn't that expand into 49 after some work?

I did see it. I tried going from 28 to 49 but I couldn't do it. Do you see how they substituted (20) into (28)? Once you do that you really have no room for changing things (at least not that I can see). I actually tried playing with different block inverse equations (wiki) and still couldn't get to (49). Do you believe (28) can be changed to (49)? I will give it a second look.

Thank you for your reply and time.

 

[jedishrfu]

My suggestion was only a cursory glance at the paper.

Rereading it a bit more they mention that 21 is a reclusive form and that they can rewrite it as 49 so now I don't think they show the derivation of 49 in the article.

Do you have any other references to the Ricatti equation? You might be able to find a source with the derivation spelled out.

 

[jedishrfu]

When you compare 21 with 49 notice that the last three terms of 49 are very similar to 21 and so it looks like they have applied some algebra to eliminate the denominator of the 21 equation. Does that make sense?

I was trying to see what they did by dropping common terms in both equations to see what's left.

Perhaps @Mark44 or @HallsofIvy could comment here.

 

[perplexabot]

Rereading it a bit more they mention that 21 is a reclusive form and that they can rewrite it as 49 so now I don't think they show the derivation of 49 in the article.

As per the (second) snippet shown in my initial post, they say they used simple algebraic manipulation! So I am assuming there exists a direct way of getting 49 from 21

Do you have any other references to the Ricatti equation? You might be able to find a source with the derivation spelled out.

I do have some riccati equation sources. And some do have proofs, but these proofs are of how the discrete algebraic riccati equation comes to be in an application specific situation (such as the kalman filter).

 

[perplexabot]

When you compare 21 with 49 notice that the last three terms of 49 are very similar to 21 and so it looks like they have applied some algebra to eliminate the denominator of the 21 equation. Does that make sense?

I was trying to see what they did by dropping common terms in both equations to see what's left.

Perhaps @Mark44 or @HallsofIvy could comment here.

I don't really see much in common. I can see that $D_n^{22}$ is in common. I can also see that $D_n^{21}$ and $D_n^{12}$ is premultiplied and postmultiplied to the rest of the terms. This makes me realize that whatever manipulation that was made, was made for $(J_n+D_n^{11})^{-1}$

I have actually done the following earlier, since we are discussing something relevant, maybe it is worth showing. Here it goes:
First, for ease of writing, let
$A = J_n$ and $B=D_n^{11}$
So according to (21) and (49)
$(A+B)^{-1} = -B^{-1}AB^{-1} + B^{-1}A(A+B)^{-1}AB^{-1}+B^{-1}$ (call this equation 1)
Doing a little bit of simple algebra on the above (premultiplying the above equation by $B \ \ and \ \ A^{-1}$) we get:
$A^{-1}B(A+B)^{-1}-(A+B)^{-1}AB^{-1} = A^{-1}-B^{-1}$ (call this equation 2)
Going back to equation 1 and again doing a little bit of algebra (this time postmultiplying by $B \ \ and \ \ A^{-1}$) we get:
$B^{-1}A(A+B)^{-1}-(A+B)^{-1}BA^{-1}=A^{-1}-B^{-1}$ (call this equation 3)

Then, for some reason I set equations 2 and 3 to each other, I get the following:
$(A^{-1}B-B^{-1}A)(A+B)^{-1}=(A+B)^{-1}(AB^{-1}-BA^{-1})$ (call this equation 4)
or writing it as
$(A^{-1}B-B^{-1}A)(A+B)^{-1}(AB^{-1}-BA^{-1})^{-1}=(A+B)^{-1}$ (call this equation 5)

This was the nice equation I was talking about. This is why I think an identity was involved. I don't believe this is of any help, but maybe someone has an idea?

 

[Mark44]

This is some pretty complicated stuff. I worked at getting from the first part of equ. 28 to the second part, and filled up four pages of notepaper without getting there. I'll take another look at it tomorrow, but it's getting late where I am, so I'm going to turn in.

 

[perplexabot]

This is some pretty complicated stuff. I worked at getting from the first part of equ. 28 to the second part, and filled up four pages of notepaper without getting there. I'll take another look at it tomorrow, but it's getting late where I am, so I'm going to turn in.

First, I want to say thank you for your time and your much needed help.
If you are talking about the two equality lines of (28) they used blockwise inverse identities:
$\begin{equation*} \begin{split} J_{n+1}&=D_n^{22}-\begin{bmatrix}0 & D_n^{21}\end{bmatrix}\begin{bmatrix}A_n & B_n\\ B_n^T &C_n+D_n^{11}\end{bmatrix}^{-1}\begin{bmatrix}0\\D_n^{12}\end{bmatrix}\\ J_{n+1}&=D_n^{22}-\begin{bmatrix}0 & D_n^{21}\end{bmatrix}\begin{bmatrix}WC & WC\\ WC & (C_n + D_n^{11}-B_n^TA^{-1}B_n)^{-1}\end{bmatrix}\begin{bmatrix}0\\D_n^{12}\end{bmatrix} \end{split} \end{equation*}$
Here, $WC$ stands for "who cares" since these blocks will be multiplied by zero and will disappear.

Have you looked at my previous message/post? Maybe it can be put to use. Or maybe it is not needed.

Thank you all. Have a good night.

 

[Mark44]

First, I want to say thank you for your time and your much needed help.
If you are talking about the two equality lines of (28) they used blockwise inverse identities:
$\begin{equation*} \begin{split} J_{n+1}&=D_n^{22}-\begin{bmatrix}0 & D_n^{21}\end{bmatrix}\begin{bmatrix}A_n & B_n\\ B_n^T &C_n+D_n^{11}\end{bmatrix}^{-1}\begin{bmatrix}0\\D_n^{12}\end{bmatrix}\\ J_{n+1}&=D_n^{22}-\begin{bmatrix}0 & D_n^{21}\end{bmatrix}\begin{bmatrix}WC & WC\\ WC & (C_n + D_n^{11}-B_n^TA^{-1}B_n)^{-1}\end{bmatrix}\begin{bmatrix}0\\D_n^{12}\end{bmatrix} \end{split} \end{equation*}$
Here, $WC$ stands for "who cares" since these blocks will be multiplied by zero and will disappear.

Yes, I got the same result for the (2, 2) entry of the matrix in the middle just above.
I did this by calculating the block inverse of $\begin{bmatrix} A_n & B_n \\ B_n^T & C_n + D_n^{11} \end{bmatrix}$

Have you looked at my previous message/post? Maybe it can be put to use. Or maybe it is not needed.

Yeah, I took a look, but I can't say whether or not that work leads anywhere. I'll keep gnawing on this awhile.

One thing bothers me that might be a typo. Right after eqn. 19 they say,

Comparison of (16) and (20) gives $J_n = C_n - B_n^TA_n^{-1}B_n$ (20)

It has to be comparison of (16) and (some other equation) that yields (20), maybe equ. 19?

 

[perplexabot]

One thing bothers me that might be a typo. Right after eqn. 19 they say,

It has to be comparison of (16) and (some other equation) that yields (20), maybe equ. 19?

Yes, I agree, that is most likely a typo. I believe they meant to say (15) and (19).

I will also be playing with this in the mean time. Let's hope we get somewhere.

 

[perplexabot]

I know this post is kind of old but I think it may be worth posting the answer (yes, I found it!) for future reference. So excuse the necromancy : p

I don't really see much in common. I can see that $D_n^{22}$ is in common. I can also see that $D_n^{21}$ and $D_n^{12}$ is premultiplied and postmultiplied to the rest of the terms. This makes me realize that whatever manipulation that was made, was made for $(J_n+D_n^{11})^{-1}$

My logic was correct here, what was manipulated was indeed $(J_n+D_n^{11})^{-1}$. And as this thread's title suggests, it is an Identity that was used! Which identity? The Woodbury matrix identity (aka, the matrix inversion lemma). I did expect this when I initially posted my question, but what I failed to see was the fact that the identity was used TWICE! Here it goes:

Using the identity shown here where first we take the following: $D_n^{11}=A$, $J_n=C$ and $U=V=I$. This gives:
$(J_n+D_n^{11})^{-1} = D_n^{11} - (D_n^{11})^{-1}(J_n^{-1}+(D_n^{11})^{-1})^{-1}(D_n^{11})^{-1}$

Then using that same identity again on $(J_n^{-1}+(D_n^{11})^{-1})^{-1}$ where we take the following: $(D_n^{11})^{-1}=C$, $J_n^{-1}=A$ and $U=V=I$. This gives:
$\begin{equation} \begin{split} (J_n+D_n^{11})^{-1} &= D_n^{11} - (D_n^{11})^{-1}(J_n-J_n(J_n+D_n^{11})^{-1}J_n)(D_n^{11})^{-1} \\ &= D_n^{11} - (D_n^{11})^{-1}J_n(D_n^{11})^{-1}-(D_n^{11})^{-1}J_n(J_n+D_n^{11})^{-1}J_n(D_n^{11})^{-1} \end{split} \end{equation}$
Now plugging in that final expression for $(J_n+D_n^{11})^{-1}$ back into equation (21), equation (49) is achieved : ) (equations (21) and (49) are shown in the original post)