Browse Prior Art Database

AN APL ALGORITHM FOR FINDING THE GENERALIZED INVERSE OF A MATRIX

IP.com Disclosure Number: IPCOM000148512D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Document File: 8 page(s) / 256K

Publishing Venue

Software Patent Institute

Related People

Sarachik, P.E.: AUTHOR [+3]

Abstract

P. E. Sarachik* and u. 0zgiiner

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 8

AN APL ALGORITHM FOR FINDING THE GENERALIZED INVERSE OF A MATRIX

P. E. Sarachik* and u. 0zgiiner

IBM Thomas J. Watson Research Center

Yorktown Heights, New York 10598

Abstract: An algorithm is given for obtaining the generalized inverse of a matrix by first transforming it into products of matrices with linearly independent rows or columns. The algorithm was developed to be used with the APL primitive function

"8". A program written in APL is included.

*Currently on leave from the Department of Electric Engineering and Electrophy- sics, Polytechnic Institute of New York, Brooklyn, New York.

[This page contains 1 picture or other non-text object]

Page 2 of 8

LIhlITED DISTRIBUTION NOTICE

This report has been submitted for publication elsewhen and has been issued as a Research Report for early dissemination
of its contents. As a courtesy to the intended publisher, it should not be widely distributed until after the date of outside publication.

Copies may be requested from:


IBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 8

Introduction

   This note describes an algorithm for obtaining the Moore-Penrose generalized inverse1 A+ of a matrix A. The algorithm was developed to be used with the APL primitive function @A (domino)z and a program written in APL is enclosed. However, the algorithm itself can be used in conjunction with any subroutine that generates (as EA in APL)

from a matrix A with linearly independent columns. EOA in APL gives a dimension error and fails whenever the columns of A are dependent. The algorithm described here finds a representation of A as the product of full rank matrices to which I
can be applied to produce the generalized

inverse A+.

   There exist a number of other algorithms in the literature (e.g. [3]) to generate the generalized inverse. The one treated here differs in assuming the availability of the operator (1).

Formulation

   Let A be an n x m matrix of rank m, and let R be the column permutation matrix such that,

where A, is nxm, and has rank m,. That is, A, consists of the m, linearly independent columns of A. Now, since the columns of A, are linear combinations of the columns of A,, we can express 4 as

for some m,x (m-m,) matrix K. In particular, K = A,+& satisfies (3) since a solution to (3) exists. Thus, using this and (3) in (2), we see that

AP = [A, AlA1+4] = A,B (4)

where B = [I A,+4] is m, xm and it is obvious that it has rank m,. Since P is a permutation matrix, it is well known that P-'=PT (where the superscript T denotes the transpose), so (4) becomes

To show that a matrix X is the Moore-Penrose generalized inverse A+ of A, it is sufficient to show that X satisfies the defining relations,

i

[This page contains 1 picture or other non-text object]

Page 4 of 8

Theorem: X = PB+A,+...