Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\bar{y} = \frac{A\bar{x} +\bar{b}}{\bar{c}^{T}\bar{x} + d}$, where $A$ is $n \times m$ matrix with $n, m \in \mathbb R_{+}$. Let $f(x) := \bar{y}$ so $f : \mathbb R^{m} \mapsto \mathbb R^{n}$. The denominator and numerator are convex and affine so $\bar{y}$ must be convex and affine because $\bar{y}$ is essentially a perspective function with affine and convex functions. $d \in \mathbb R$ is scalar.

I want to calculate its inverse.

Switch $\bar{x}$ to $\bar{y}^{-1}$ and $\bar{y}$ to $\bar{x}$ and solve.

$$\bar{x}(\bar{c}^{T}\bar{y}^{-1}+d) - A\bar{y}^{-1} - \bar{b} = 0$$

$$(\bar{x} \bar{c}^{T} - A ) \bar{y}^{-1} + (\bar{x} d - \bar{b} ) = 0$$

So

$$\bar{y}^{-1} = (\bar{x} \bar{c}^{T} -A)^{-1}(\bar{b} - \bar{x} d)$$

if $(\bar{x} \bar{c}^{T} -A)$ is invertible.

Alert:

$$\bar{x}(\bar{c}^{T}\bar{y}^{-1}) = (\bar{x}\bar{c}^{T})\bar{y}^{-1}$$ where $c^{T}\bar{y}^{-1}$ is contant but the dimensions with $\bar{x}\bar{c}^{T}$ may not match. Something very wrong here, any rescue? Evidently I should have certain assumptions about the dimensions so that the operations above are correct. Is there some easy way to find the inverse mapping for the function $\bar{y}$?

share|improve this question
    
How did you get from the first line to the second? –  Rahul Sep 20 '11 at 19:15
    
@RahulNarain: now understable? Corrected a random err. –  hhh Sep 20 '11 at 19:19
1  
You cannot "divide" by a matrix. You can multiply by its inverse if it exists, so more appropriate would be $y^{-1} = (xc^T - A)^{-1}(xd - b)$. –  TMM Sep 20 '11 at 19:26
    
@ThijsLaarhoven: yes, you are right about that. Now more correct? –  hhh Sep 20 '11 at 19:31
1  
@hhh: Actually, no. If $Ax = b$, then we can isolate $x$ by multiplying both equations with $A^{-1}$ from the left. So then $x = (A^{-1}A)x = A^{-1}(Ax) = A^{-1}b$. You multiplied from the right with $A^{-1}$, which is not only dimensionally impossible but also does not give you $(Ax)A^{-1} = x$. –  TMM Sep 20 '11 at 19:44

2 Answers 2

up vote 2 down vote accepted

This can be seen as a Möbius transformation where the variable is real valued vector instead of a complex scalar.

Define the Möbius transformation as follows: $$ \Delta\star\pmatrix{P&Q\\R &S} = P+Q\Delta(I-S\Delta)^{-1}R $$ for $P,Q,R,S$ matrices over $\mathbb{R}$. (assuming compatible dimensions)

It is just notation don't worry about the commutativity etc. properties. Notice how it coincides with the Wiki link if you assume the matrices and $\Delta$ are scalars. (So you can perform a division)

In your case, the matrix associated with the transformation is $$ y=x\star \left(\begin{array}{c|cc}0 &A &b\\\hline 1 & -c^T&0\end{array} \right) $$ where $$x=\pmatrix{\bar{x}\\1} $$ For the inverse of the transformation to exist, we need the matrix to be invertible. And that can only happen (check the determinant along the first column) if the matrix $\pmatrix{A &b}$ is invertible. Let $V^{-1} := \pmatrix{A&b}$ and also partition $V=\pmatrix{V_1\\V_2}$ compatible with $\pmatrix{c^T&0}$. Then the big matrix inverse becomes $$ \left(\begin{array}{ccc}0 &A &b\\ 1 & -c^T&0\end{array} \right)^{-1} = \left(\begin{array}{cc}c^TV_1 &1\\ V_1&0\\ V_2 &0\end{array} \right) $$

Please note that the zero blocks are of different sizes now. I have to again partition this matrix by the first column/$m+2$ rows, but it would look horrible so I will just give the general form and you can fill in the rest. The inverse transformation can be computed as, $$ x=y\star\left(\begin{array}{c|c}\bar{p}&Q\\\hline r &\bar{s}^T\end{array} \right) = \bar{p} + Qy(1-\bar{s}^Ty)^{-1}r $$

Long story short you have to compute the inverse of the matrix that is associated with the Möbius transformation. Therefore, you need assumptions that prevent the degenerate cases.

share|improve this answer

I don't like the notation $\bar{y}^{-1}$. If $f(x) = \dfrac{A x + b}{c^T x + d} = y$ (where $A$ is an $n \times n$ matrix, $x$, $y$, $b$ and $c$ are $n$-vectors, $d$ is a scalar, and $c^T x + d \ne 0$), then $A x + b = (c^T x + d) y$ so $(A - y c^T) x = d y - b$. Thus if $A - y c^T$ is invertible, $$ x = f^{-1}(y) = (A - y c^T)^{-1} (d y - b)$$

share|improve this answer
    
$A$ is $n \times n$ matrix if $m=n$. $A$ is $n \times m$ matrix where $n, m \in \mathbb R_{+}$. The only restriction is the convexity and affinity, noted at the very bottom. –  hhh Sep 20 '11 at 19:33
1  
If the matrix is not square, you could try using $x = (A^TA)^{-1}(A^TA)x = (A^TA)^{-1}A^T(Ax) = (A^TA)^{-1}A^Tb$ to go from an equation of the form $Ax = b$ to $x = (A^TA)^{-1}A^Tb$. –  TMM Sep 20 '11 at 20:03
    
yes the notation is bad with $\bar{y}^{-1}$ because $\bar{y}$ is a vector and you cannot take an inverse of a vector, +1. It is inverse of the function $\bar{y}$. Am I clear now? Let $\bar{y} = f(x)$ so $f^{-1}(x)$ is the inverse, certainly less confusing. –  hhh Sep 20 '11 at 20:32
    
@ThijsLaarhoven: let $\bar{k} := \bar{b} - \bar{y}d$ and $H := \bar{y} \bar{c}^{T} - A$. So $f^{-1} = (H^{T}H)^{-1} H^{T} \bar{k}$. How can you know now whether $f^{-1}$ even exists? –  hhh Sep 20 '11 at 20:41
1  
If $A$ is $n \times m$ with $n < m$, solutions to $Ax=b$, if they exist, will never be unique. If $n > m$, solutions to $Ax=b$ will not exist for most $b$. But if $A$ has rank $m$, $A^T A$ will be invertible and Thijs's solution gives the solution to $Ax=b$ when it exists. You might look up "Moore-Penrose pseudoinverse". –  Robert Israel Sep 21 '11 at 0:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.