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.

$A$ is a nondegenerate $n \times n$ matrix with real-valued entries. If we interpret the rows of $A$ as points in $\mathbb{R}^n$, then $A$ defines a unique hyperplane that passes through each of these points (this hyperplane does not necessarily pass through the origin). Let $v$ be the normal vector to this hyperplane (to make $v$ unique, we can introduce the normalization that $\sum v_i = 1$).

How can I find an expression for $\frac{dv}{dA_{ij}}$?

share|improve this question
    
By definition, a hyperplane has dimension $n-1$. Are you assuming the matrix $A$ has rank $n-1$? –  Git Gud Jan 26 '13 at 19:06
    
No, I'm not. It takes $n-1$ vectors to define a hyperplane, but it takes $n$ points to define a hyperplane. We are interpreting $A$ as a matrix of points, not vectors (that's why the hyperplane does not need to pass through the origin). –  GMB Jan 26 '13 at 19:08
    
Ahh!!! Got you. –  Git Gud Jan 26 '13 at 19:11
    
I think your normalization $\sum v_i=1$ is a bad idea: there is no way to normalize $[1,-1]$. The usual normalization is $\lVert v\rVert^2=v^Tv=1$ instead. –  Rahul Jan 26 '13 at 22:29
    
Generally I'd agree, but the normalization $\sum v_i = 1$ isn't entirely arbitrary - I actually need my final $v$ to have that property. In my particular use for this problem, I will only consider matrices that result in $v \ge 0$ (pointwise). –  GMB Jan 26 '13 at 23:00

2 Answers 2

I'm answering my own question (I hope that's within the M.SE etiquette) - I think I've found a partial solution.

Assuming $A$ is nonsingular, the normal vector is given by $v(A) = A^{-1}*1^T$ (I'm not sure why this is true, but I coded a quick simulation to test it and it checks out). We can normalize with $v(A) = \frac{A^{-1}*1^T}{1*A^{-1}*1^T}$, and then apply the standard rules of matrix calculus to get a solution from here:

$$\frac{dv}{dA_{ij}} = (\frac{d(1*A^{-1}*1^T)^{-1}}{dA_{ij}}) A^{-1}*1^T + (1*A^{-1}*1^T)^{-1}(\frac{d(A^{-1}*1^T)}{dA_{ij}})$$

$$ = (-\frac{d(1*A^{-1}*1^T)}{dA_{ij}})^{-2} A^{-1}*1^T + (1*A^{-1}*1^T)^{-1}(\frac{dA^{-1}}{dA_{ij}})*1^T$$

$$ = (-\frac{d(1*A^{-1}*1^T)}{dA_{ij}})^{-2} A^{-1}*1^T + (1*A^{-1}*1^T)^{-1}(\frac{dA^{-1}}{dA_{ij}})*1^T$$

$$ = (-1*\frac{dA^{-1}}{dA_{ij}}*1^T)^{-2} A^{-1}*1^T + (1*A^{-1}*1^T)^{-1}(\frac{dA^{-1}}{dA_{ij}})*1^T$$

$$ = (-1*\frac{dA^{-1}}{dA_{ij}}*1^T)^{-2} A^{-1}*1^T + (1*A^{-1}*1^T)^{-1}(\frac{dA^{-1}}{dA_{ij}})*1^T$$

$$ = (1*A^{-1}*\frac{dA}{dA_{ij}}*A^{-1}*1^T)^{-2} A^{-1}*1^T - (1*A^{-1}*1^T)^{-1}(A^{-1}*\frac{dA}{dA_{ij}}*A^{-1}*1^T)$$

Turns out that $A^{-1}*\frac{dA}{dA_{ij}}*A^{-1}*1^T = (\sum_{y=1}^n A^{-1}_{jy}) (A^{-1}_{*i})$.

$$ = (1*(\sum_{y=1}^n A^{-1}_{jy}) (A^{-1}_{*i}))^{-2} A^{-1}*1^T - (1*A^{-1}*1^T)^{-1}(\sum_{y=1}^n A^{-1}_{jy}) (A^{-1}_{*i})$$

$$ = ((\sum_{y=1}^n A^{-1}_{jy}) (\sum_{x=1}^n A^{-1}_{xi}))^{-2} A^{-1}*1^T - (\sum_{x=1}^n \sum_{y=1}^n A^{-1}_{xy})^{-1}(\sum_{y=1}^n A^{-1}_{jy}) (A^{-1}_{*i})$$

Alright, that's all the simplifying I'm going to do - I really hope my algebra went okay. Hopefully this is helpful to someone else.

share|improve this answer

This is not really a different answer but a couple of comments on your existing one. Also, I apologize for not adopting your row-vector convention, but I can only think in terms of column vectors... Hopefully it's not too annoying for you to translate mentally.

  1. Let $P=A^T$ be the matrix whose columns are your points $p_1, \ldots, p_n$ in $\mathbb R^n$. Here is a proof that $A^{-1}1=P^{-T}1$ is indeed normal to the hyperplane defined by the $p_i$, where $1$ is a column vector with all ones. Observe that a vector $v$ is normal to said hyperplane if and only if it is normal to all $p_i-p_j$, that is, $v^T(p_i-p_j)=0$. Let $q=P^{-T}1$. We have $$q^T(p_i-p_j)=1^TP^{-1}(p_i-p_j)=1^T(e_i-e_j)=0,$$ where $e_i$ and $e_j$ are the basis unit vectors, because $1^Te_i=1^Te_j=1$ (the scalar $1$).

  2. You would have an easier time differentiating if you did it in two steps. Let $q=A^{-1}1$ as before, and $n=q/(1^Tq)$. We already know that $$\frac{\partial q}{\partial A_{ij}}=\frac{\partial A^{-1}}{\partial A_{ij}}1=A^{-1}\frac{\partial A}{\partial A_{ij}}A^{-1}1=A^{-1}E_{ij}A^{-1}1,$$ where $E_{ij}$ is the matrix with $1$ in the $(i,j)$th entry and $0$ elsewhere. Now we want to find $\partial n/\partial A_{ij}$. To simplify things, let us denote differentiation by $A_{ij}$ with a prime ($'$). Then $$n'=\left(\frac q{1^Tq}\right)'=\frac{q'(1^Tq)-q(1^Tq)'}{(1^Tq)^2}=\frac{(1^Tq)q'-q1^Tq'}{(1^Tq)^2}=\left(I-\frac{q1^T}{1^Tq}\right)\frac{q'}{1^Tq}=\big(I-n1^T\big)\frac{q'}{1^Tq}.$$

share|improve this answer
    
Thanks - this is very helpful. I think something went minorly wrong in the algebra at the very end: you want $\frac{(1^T q)q' - (1^T q')q}{(1^T q)^2}$ –  GMB Jan 27 '13 at 19:31
    
@LevDub: That's the same as my $\dfrac{(1^Tq)q'-q1^Tq'}{(1^Tq)^2}$, because $(1^Tq')q=q(1^Tq')$. –  Rahul Jan 27 '13 at 19:41
    
I agree, but that makes the next step incorrect: you've implicitly factored $q(1^T q')$ as $(q1^T)q'$. This is causing the term $(I - \frac{q 1^T}{1^T q})$, which doesn't make sense: $I$ is a matrix and $\frac{q 1^T}{1^T q}$ is a scalar. –  GMB Jan 27 '13 at 20:03
    
@LevDub: Sorry for changing the convention you were using. I'm working with column vectors, so $q1^T$ is a matrix. In column/row-agnostic notation, it's $q\otimes1$. –  Rahul Jan 27 '13 at 20:07
    
Ahhh, you're completely right, I understand now. Thanks. –  GMB Jan 27 '13 at 20:08

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.