# A unified approach for the recursive determination of generalized inverses

Firdaus Udwadia, Robert Kalaba

► To cite this version:

Firdaus Udwadia, Robert Kalaba. A unified approach for the recursive determination of generalized inverses. Computers & Mathematics with Applications, 1999, 37 (1), pp.125 - 130. 10.1016/S0898-1221(98)00247-8. hal-01403605

HAL Id: hal-01403605

https://hal.science/hal-01403605

Submitted on 26 Nov 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Unified Approach for the Recursive Determination of Generalized Inverses

F. E. UDWADIA

Department of Mechanical Engineering, Civil Engineering, and Decision Systems
University of Southern California, Los Angeles, CA 90089-1453, U.S.A.

R. E. KALABA

Department of Biomedical Engineering and Economics
University of Southern California, Los Angeles, CA 90089, U.S.A.

**Abstract**—Using a unified approach, simple derivations for the recursive determination of different types of generalized inverses of a matrix are presented. These include results for the generalized inverse, the least-squares generalized inverse, the minimum-norm generalized inverse, and the Moore-Penrose inverse of a matrix. © 1998 Elsevier Science Ltd. All rights reserved.

**Keywords**—Generalized inverses, Recursive determination, Unified approach, Dynamic programming.

## 1. INTRODUCTION

The recursive determination of a generalized inverse of a matrix finds extensive applications in the fields of statistical inference [1-3], filtering theory, estimation theory [4], and system identification [5]. More recently, generalized inverses have found renewed applicability in the field of analytical dynamics [6,7]. The reason for the extensive applicability of recursive relations is that they provide a systematic method to generate 'updates' whenever sequential addition of data or new information becomes available, and updated estimates which take into account this additional information are required.

The recursive scheme for the computation of the Moore-Penrose (MP) inverse [8,9] of a matrix was ingeniously obtained in a famous paper by Greville in 1960 [2]. Because of its extensive applicability, Greville's result is widely stated in almost every book that touches on the subject of generalized inverses of matrices. Yet, because of the complexity of his solution technique, Greville's proof is seldom, if ever, quoted or outlined, even in specialized texts which deal solely with generalized inverses of matrices. For example, in books like [4,10-12], Greville's result is stated, but no constructive proof is provided, most likely because of its perceived complexity.

In the same vein, Mitra and Bhimasankaram [13] provide several results for the recursive determination of generalized inverses of matrices; they state their results as several *Ansätze* and prove them by directly verifying their validity using a number of specialized results related to generalized inverses of matrices. Their results are equivalent to those presented here. However, they provide no constructive proofs for their results and their proofs for the various types of gen-
eralized inverses have no underlying reasoning or thread running through them; only verifications of the various *Ansätze* are carried out.

In this paper, we present a simple constructive approach inspired in part by Bellman's optimality principle, to the recursive determination of various generalized inverses of a matrix. The approach relies on a unified underlying theme and shows clearly why and how the differences in the recursive forms of the various generalized inverses arise. Thus, our results encompass those of Greville [2], and our method of proof, being constructive, provides deeper insights into the nature of the recursive determination of generalized inverses.

For convenience, we introduce the following notation. Given a real matrix $A$, its MP-inverse $G$ satisfies the following four conditions:

(1) $AGA = A$,

(2) $GAG = G$,

(3) $AG$ is symmetric, and

(4) $GA$ is symmetric.

We shall denote a matrix $G$ which satisfies all four of these conditions by $A^{\{1,2,3,4\}}$. Similarly, a matrix which satisfies only the first and fourth condition above shall be denoted as $A^{\{1,4\}}$ and shall be referred to as the $\{1,4\}$-inverse of $A$, etc.

The most commonly used generalized inverses of a matrix are the MP-inverse (also denoted here as the $\{1,2,3,4\}$-inverse), the $\{1,3\}$-inverse, the $\{1,4\}$-inverse, and the $\{1\}$-inverse because these inverses are relevant to the solution $x$ of the matrix equation $Ax = b$ or of the relation $Ax \approx b$. We shall begin by *defining* these generalized inverses (as in [12]) in terms of the relevant linear relations which they help solve. The MP-inverse provides the minimum-length solution $x = A^{\{1,2,3,4\}}b$ in the set of least-squares solutions of the possibly inconsistent equation $Ax \approx b$ for any $b$, the $\{1,3\}$-inverse provides a least-squares solution $A^{\{1,3\}}b$ to the possibly inconsistent equation $Ax \approx b$ for any $b$, the $\{1,4\}$-inverse provides a minimum-length solution $A^{\{1,4\}}b$ for any $b$ for which the equation is consistent, and the $\{1\}$-inverse of $A$ provides a solution $A^{\{1\}}b$ for any $b$ for which the equation $Ax = b$ is consistent. This paper is concerned with these four commonly used generalized inverses defined above, which we shall denote, in general, by $A^*$. The solution $x$ is then expressed, in general, as $A^*b$. Their generalized forms are given in [14].

Given a real $m$ by $k$ matrix $A_k$, one can partition it as $[A_{k-1} \ a]$ where $A_{k-1}$ consists of the first $(k-1)$ columns of the matrix $A_k$ and $a$ is its last column. The column vector $a$ comprises ‘new’ or additional information, while the matrix $A_{k-1}$ comprises accumulated past data. The generalized inverse $A_k^*$ of the updated matrix $A_k$ is then sought in terms of the generalized inverse $A_{k-1}^*$ of the matrix $A_{k-1}$ which corresponds to past accumulated data, and the vector $a$ containing new or additional information. The MP-inverse of a matrix $A$ is unique. The other generalized inverses which we shall deal with here are not in general unique, and so, in what follows, by say $A_{k-1}^{\{1,4\}}$, we shall mean any one of the set of $\{1,4\}$-inverses of the matrix $A_{k-1}$.

## 2. MAIN RESULT

Let $A_k = [A_{k-1} \ a]$ be an $m$ by $k$ matrix whose last column is $a$. Let the $m$-vector $c = (I - A_{k-1}A_{k-1}^*)a$ and let the $m$-vector $d = (A_{k-1}^*)^T A_{k-1}^* a / (1 + a^T (A_{k-1}^*)^T A_{k-1}^* a)$. Then,

$$A_k^* = \begin{bmatrix} A_{k-1}^* - A_{k-1}^* a u^T \\ u^T \end{bmatrix}, \quad \text{for } c \neq 0 \qquad (1a)$$

and

$$A_k^* = \begin{bmatrix} A_{k-1}^* - A_{k-1}^* a v^T \\ v^T \end{bmatrix}, \quad \text{for } c = 0, \qquad (1b)$$

when we have the following.
$$
\text{Part 1: } * = \{1, 2, 3, 4\}, \qquad u^T = \frac{c^T}{c^\top c}, \qquad \text{and } v = d. \tag{2}
$$

$$
\text{Part 2: } * = \{1, 3\}, \qquad u^\top = \frac{c^\top}{c^\top c}, \qquad \text{and } v = \text{any arbitrary } m\text{-vector } q. \tag{3}
$$

$$
\text{Part 3: } * = \{1, 4\}, \qquad u^\top = \frac{c^\top (I - A_{k-1} A_{k-1}^*)}{c^\top c}, \qquad \text{and } v = d. \tag{4}
$$

$$
\text{Part 4: } * = \{1\}, \qquad u^\top = \frac{c^\top (I - A_{k-1} A_{k-1}^*)}{c^\top c}, \qquad \text{and } v = \text{any arbitrary } m\text{-vector } q. \tag{5}
$$

From equations (1a) and (1b), notice that the form of the inverse $A_{k-1}^*$ is the same for $c=0$ and for $c \neq 0$. We have used separate equations here only for convenience.

PROOF OF PART 1. We consider the solution of the least squares problem

$$
A_k x = [A_{k-1} \quad a] \begin{bmatrix} z \\ s \end{bmatrix} = A_{k-1} z + a s \approx b, \quad (6)
$$

where we have partitioned the vector $x$ into the $(k-1)$-vector $z$ and the scalar $s$. To determine
the minimum-length-least-squares solution $x$ of $A_k x \approx b$, we consider all those pairs $(z, s)$ which
minimize $J(z, s) = \|A_{k-1}z + as - b\|_2^2$, and from these pairs select the one whose length $z^\top z + s^2$
is a minimum.

We begin by setting $s = s_o$, where $s_o$ is some fixed scalar. Thus, we have

$$
J(z, s_o) = \| A_{k-1}z - (b - as_o) \|_2^2. \tag{7}
$$

Minimizing (7) such that $\hat{z}^\top \hat{z}$ is also a minimum from among all $(k-1)$-vectors $z$, we obtain,
from the definition of the MP-inverse,

$$
\hat{z}(s_o) = A_{k-1}^{\{1,2,3,4\}} (b - as_o). \quad (8)
$$

Thus, for a given value of the scalar $s_o$, the $(k-1)$-vector $\hat{z}$ is a function of $s_o$. Using equation (8) in equation (7), we can now find $s_o$ such that

$$
\begin{align}
J(\hat{z}(s_o), s_o) &= \left\| A_{k-1} A_{k-1}^{\{1,2,3,4\}} (b - as_o) + as_o - b \right\|_2^2 \nonumber \\
&= \left\| (I - A_{k-1} A_{k-1}^{\{1,2,3,4\}}) as_o - (I - A_{k-1} A_{k-1}^{\{1,2,3,4\}}) b \right\|_2^2 \tag{9}
\end{align}
$$

is a minimum. Depending on $c = (I - A_{k-1}A_{k-1}^{\{1,2,3,4\}})a$, we must now deal with two cases: the
first when $c \neq 0$; the second when $c = 0$. The first case occurs when $a$ does not lie in the column
space of $A_{k-1}$; the second, when the vector $a$ lies in the column space of the matrix $A_{k-1}$.

(i) For $c \neq 0$, the unique value of $s_o$ which minimizes (9) is given by

$$
\begin{align}
\tilde{s}_o &= \frac{a^\top (I - A_{k-1} A_{k-1}^{\{1,2,3,4\}}) (I - A_{k-1} A_{k-1}^{\{1,2,3,4\}}) b}{c^\top c} \tag{10} \\
&= \frac{c^\top}{c^\top c} b = c^{\{1,2,3,4\}} b = u^\top b, \notag
\end{align}
$$

where in the first equality, we have used the fact that the matrix $(I - A_{k-1}A_{k-1}^{\{1,2,3,4\}})$ is
symmetric, and in the second equality, that it is idempotent. Having found the unique
value $\tilde{s}_o$ which minimizes (9), we now obtain from (8), the minimum-length-least-squares
solution of $A_k x \approx b$ as

$$
x = A_k^{\{1,2,3,4\}} b = \begin{bmatrix} \hat{z}(\tilde{s}_o) \\ \tilde{s}_o \end{bmatrix} = \begin{bmatrix} A_{k-1}^{\{1,2,3,4\}} - A_{k-1}^{\{1,2,3,4\}} a u^T \end{bmatrix} b, \quad (11)
$$
where the first equality follows by the definition of the MP-inverse. Hence,

$$A_k^{\{1,2,3,4\}} = \left[ \begin{array}{c} A_{k-1}^{\{1,2,3,4\}} - A_{k-1}^{\{1,2,3,4\}} a u^\top \\ u^\top \end{array} \right], \quad \text{for } c \neq 0. \qquad (12)$$

(ii) For $c = 0$, we observe from equation (9) that $J(\hat{z}(s_o), s_o)$ is not a function of $s_o$. Thus, we only need to minimize $J_1(s_o) = \hat{z}(s_o)^\top \hat{z}(s_o) + s_o^2$ over all values of $s_o$, where $\hat{z}(s_o)$ is given in equation (8). For convenience, we can write this as

$$J_1(s_o) = s_o^2 + s_o^2 p_1^\top p_1 - 2s_o p_1^\top p_2 + p_2^\top p_2, \qquad (13)$$

where we have denoted $p_1 = A_{k-1}^{\{1,2,3,4\}} a$ and $p_2 = A_{k-1}^{\{1,2,3,4\}} b$. The scalar value $\tilde{s}_o$, which minimizes $J_1(s_o)$ is then given by

$$\tilde{s}_o = \frac{p_1^\top p_2}{(1 + p_1^\top p_1)} = \frac{a^\top (A_{k-1}^{\{1,2,3,4\}})^\top A_{k-1}^{\{1,2,3,4\}}}{1 + a^\top (A_{k-1}^{\{1,2,3,4\}})^\top A_{k-1}^{\{1,2,3,4\}} a} = \nu^\top b. \qquad (14)$$

Using equation (8) to obtain $\hat{z}(\tilde{s}_o)$, we get

$$x = A_k^{\{1,2,3,4\}} b = \begin{bmatrix} \hat{z}(\tilde{s}_o) \\ \tilde{s}_o \end{bmatrix} = \begin{bmatrix} A_{k-1}^{\{1,2,3,4\}} - A_{k-1}^{\{1,2,3,4\}} a \nu^\top \\ \nu^\top \end{bmatrix} b, \qquad (15)$$

from which it follows, as before, that

$$A_k^{\{1,2,3,4\}} = \begin{bmatrix} A_{k-1}^{\{1,2,3,4\}} - A_{k-1}^{\{1,2,3,4\}} a \nu^\top \\ \nu^\top \end{bmatrix}, \quad \text{for } c = 0. \qquad (16)$$

This proves the first part of our result given in (2).

PROOF OF PART 2. The {1,3}-inverse provides a least-squares solution $x = A_k^{\{1,3\}} b$ to the equation $A_k x \approx b$. As before, we partition the vector $x$ into a $(k-1)$-vector $z$ and a scalar $s$. For a fixed $s_o$, we minimize

$$J(z, s_o) = \|A_{k-1}z - (b - as_o)\|_2^2 \qquad (17)$$

to yield

$$\hat{z}(s_o) = A_{k-1}^{\{1,3\}} (b - as_o), \qquad (18)$$

for some {1,3}-inverse of the $m$ by $(k-1)$ matrix $A_{k-1}$. We next minimize

$$\begin{align}
J(\hat{z}(s_o), s_o) &= \| A_{k-1} A_{k-1}^{\{1,3\}} (b - as_o) + as_o - b \|_2^2 \tag{19} \\
&= \| (I - A_{k-1} A_{k-1}^{\{1,3\}}) as_o - (I - A_{k-1} A_{k-1}^{\{1,3\}}) b \|_2^2, \nonumber
\end{align}$$

with respect to $s_o$ and again need to consider two cases: when $c \neq 0$ and where $c = 0$.

(i) For $c \neq 0$, we obtain the unique value of $s_o$ which minimizes (19) to be

$$\tilde{s}_o = \frac{a^\top (I - A_{k-1} A_{k-1}^{\{1,3\}}) (I - A_{k-1} A_{k-1}^{\{1,3\}})}{c^\top c} = u^\top b, \qquad (20)$$

where we have again used the fact that the matrix $(I - A_{k-1} A_{k-1}^{\{1,3\}})$ is symmetric and idempotent. Following the same sort of steps as before, we then obtain the required result for this case.

(ii) For $c = 0$, equation (19) shows that $J(\hat{z}(s_o)s_o)$ is not a function of $s_o$; hence, the choice of $s_o$ is arbitrary. If we let $s_o = q^\top b$, where $q$ is any arbitrary $m$-vector, we obtain statement (3) of our result for this case. The matrix $A_k^{\{1,3\}}$ so obtained is not unique. Moreover, once a {1,3}-inverse is obtained through the use of equations (1a), (1b), and (3), other {1,3}-inverses may be generated by adding to this {1,3}-inverse any matrix $R$ such that $A_k R = 0$.
PROOF OF PART 3. The {1,4}-inverse provides a minimum length solution $x = A_k^{\{1,4\}}b$ to the consistent equation $A_kx = b$. Again we partition the vector $x$ into a $(k-1)$-vector $z$ and a scalar $s$. For a fixed $s_o$, we solve the consistent equation

$$A_{k-1}z = b - as_o, \qquad (21)$$

yielding the minimum length solution

$$\hat{z}(s_o) = A_{k-1}^{\{1,4\}}(b - as_o) \qquad (22)$$

for some {1,4}-inverse of $A_{k-1}$. We now use equation (22) in equation (21) so that

$$(I - A_{k-1} A_{k-1}^{\{1,4\}}) as_o = (I - A_{k-1} A_{k-1}^{\{1,4\}}) b, \qquad (23)$$

obtaining the two cases $c = (I - A_{k-1} A_{k-1}^{\{1,4\}})a \neq 0$, and $c = (I - A_{k-1} A_{k-1}^{\{1,4\}})a = 0$ as before.

(i) For $c \neq 0$, the solution of the consistent equation (23) yields

$$s_o = \frac{c^\top (I - A_{k-1} A_{k-1}^{\{1,4\}})}{c^\top c} b = u^\top b, \qquad (24)$$

from which the result for this case follows on using equation (22).

(ii) For $c = 0$, both the left- and the right-hand sides of equation (23) are zero. We then need to find $s_o$ so as to minimize $J_1(s_o) = \hat{z}(s_o)^\top \hat{z}(s_o) + s_o^2$, where $\hat{z}(s_o)$ is given by equation (22). Setting $p_1 = A_{k-1}^{\{1,4\}}a$ and $p_2 = A_{k-1}^{\{1,4\}}b$, and following the reasoning in Part 1, Case (ii), we obtain the result given in (4).

We note in passing that the vector $b$ must lie in the range space of the matrix $A_k$. Using the {1,4}-inverse obtained from equation (1a), (1b), and (4), others can be obtained by adding to this {1,4}-inverse any matrix $L$ which satisfies the relation $LA_k = 0$. (See [14].)

PROOF OF PART 4. The {1}-inverse provides a solution $x = A_k^{\{1\}}b$ to the consistent equation $A_kx = b$. Partitioning the vector $x$ as before, for a fixed $s = s_o$, we obtain equation (21), whose solution now is given by

$$\hat{z}(s_o) = A_{k-1}^{\{1\}}(b - as_o), \qquad (25)$$

for some {1}-inverse of $A_{k-1}$.

Using this result in (21), we obtain

$$(I - A_{k-1} A_{k-1}^{\{1\}}) as_o = (I - A_{k-1} A_{k-1}^{\{1\}}) b. \qquad (26)$$

When $c = (I - A_{k-1} A_{k-1}^{\{1\}})a \neq 0$, the unique solution of (26) is

$$s_o = \frac{c^\top (I - A_{k-1} A_{k-1}^{\{1\}})}{c^\top c} b = u^\top b. \qquad (27)$$

From this, result (5) follows for this case. When $c = 0$, as in Part 3, both the left- and right-hand sides of the consistent equation (26) are zero; hence, $s_o$ can be arbitrary. We can then choose $s_o$ to equal $q^\top b$ where $q$ is any arbitrary $m$-vector yielding the result provided for this case in (5).

Again as in Parts 2 and 3 above, the {1}-inverse obtained from equations (1a), (1b), and (5) can be used to obtain other {1}-inverses by adding to this {1}-inverse any matrix $(L+R)$ where $L$ is such that $LA_k = 0$ and $R$ is such that $A_k R = 0$. (See [14].)
### 3. CONCLUSIONS

In this paper, we present a unified approach for obtaining recursive relations for several of the commonly used generalized inverses of an $m$ by $k$ matrix $A$. Part 1 of our main result which deals with the MP-inverse was obtained by Greville [2], but in a more complex manner; our proof of this part is substantially simpler. The unifying theme used in this paper is brought about by defining generalized inverses in terms of the solution(s) $x = A*b$ of the matrix equation $Ax = b$ or of the relation $Ax \approx b$, and then using a procedure akin to dynamic programming. This results in similar lines of reasoning for obtaining recursive relations for the various types of generalized inverses, while providing insight into why and how the differences among them arise.

### REFERENCES

1. C.R. Rao, A note on a generalized inverse of a matrix with applications to problems in mathematical statistics, *Journal of Royal Statis. Society, Ser. B* **24**, 152-158 (1962).

2. T.N.E. Greville, Some applications of the pseudoinverse of a matrix, *SIAM Review* **2**, 15-22 (1960).

3. T.N.E. Greville, Note on fitting of functions of several independent variables, *SIAM J. Appl. Math.* **9**, 249-253 (1966).

4. F. Graybill, *Matrices and Applications to Statistics*, Second edition, Wadsworth, Belmont, CA, (1983).

5. R.E. Kalaba and F.E. Udwadia, Associative memory approach to the identification of structural and mechanical systems, *Jour. Optimization Theory and App.* **76**, 207-223 (1993).

6. F.E. Udwadia and R.E. Kalaba, A new perspective on constrained motion, *Proc. Roy. Soc. of London, Series A* **439**, 407-410 (1992).

7. J.N. Franklin, Least squares solution of equations of motion under inconsistent constraints, *Linear Algebra and Its Applications* **222**, 9-13 (1995).

8. R.A. Penrose, A generalized inverse for matrices, *Proc. Cambridge Philos. Soc.* **51**, 406-413 (1955).

9. E.H. Moore, On the reciprocal of the general algebraic matrix, *Bull. Amer. Math. Soc.* **26**, 394-395 (1920).

10. A. Albert, *Regression and the Moore-Penrose Pseudoinverse*, Academic Press, New York, (1972).

11. R.M. Pringle and A.A. Rayner, *Generalized Inverse Matrices*, Hafner, New York, (1971).

12. C.R. Rao and S.K. Mitra, Further contributions to the theory of generalized inverse of matrices and its applications, *Sankhya* **33**, 289-300 (1971).

13. S.K. Mitra and P. Bhimasankaram, Generalized inverses of partitioned matrices and recalculation of least squares estimates for data or model changes, *Sankhya* **33**, 395-410 (1971).

14. F.E. Udwadia and R.E. Kalaba, *Analytical Dynamics: A New Approach*, Cambridge University Press, (1996).

15. C.R. Rao and S.K. Mitra, *Generalized Inverse of Matrices and Its Applications*, Wiley, New York, (1971).