2
$\begingroup$

$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}}$?

$\endgroup$
5
  • $\begingroup$ By definition, a hyperplane has dimension $n-1$. Are you assuming the matrix $A$ has rank $n-1$? $\endgroup$
    – Git Gud
    Jan 26, 2013 at 19:06
  • $\begingroup$ 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). $\endgroup$
    – GMB
    Jan 26, 2013 at 19:08
  • $\begingroup$ Ahh!!! Got you. $\endgroup$
    – Git Gud
    Jan 26, 2013 at 19:11
  • $\begingroup$ 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. $\endgroup$
    – user856
    Jan 26, 2013 at 22:29
  • $\begingroup$ 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). $\endgroup$
    – GMB
    Jan 26, 2013 at 23:00

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
1
$\begingroup$

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}.$$

$\endgroup$
5
  • $\begingroup$ 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}$ $\endgroup$
    – GMB
    Jan 27, 2013 at 19:31
  • $\begingroup$ @LevDub: That's the same as my $\dfrac{(1^Tq)q'-q1^Tq'}{(1^Tq)^2}$, because $(1^Tq')q=q(1^Tq')$. $\endgroup$
    – user856
    Jan 27, 2013 at 19:41
  • $\begingroup$ 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. $\endgroup$
    – GMB
    Jan 27, 2013 at 20:03
  • $\begingroup$ @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$. $\endgroup$
    – user856
    Jan 27, 2013 at 20:07
  • $\begingroup$ Ahhh, you're completely right, I understand now. Thanks. $\endgroup$
    – GMB
    Jan 27, 2013 at 20:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .