9
$\begingroup$

Napier's method of logarithms and corresponding tables of logarithms provided a important tool to simplify hand computation by converting multiplication and division to equivalent problems of addition and subtraction.

Suppose I have a linear equation for $x$:

$$ a x = b $$

While it would be overkill, if I wanted to avoid division by $a$ I could log transform both sides and use the convenient property converting products to sums

$$ \log(a) + \log(x) = \log(b) $$

then subtract $\log(a)$ and express the solution as

$$ x = \exp(\log(b) - \log(a)) .$$

Consider the matrix equation

$$ A X = B $$

where $A, X, B$ are square matrices. Under certain conditions we can compute logarithms of square matrices; the convenient products-to-sums property only holds for matrices which commute, but if A commutes with X then we have

$$ \log(A) + log(X) = \log(B) $$

$$ X = \exp(\log(B) - \log(A)) $$

What about when $x$ is a vector? Is there an analogous method to solve the system $$ A \vec{x} = \vec{b} \ \ \ ?$$

I don't believe it's possible to exponentiate a vector, let alone take its logarithm. Eigenvalue decomposition would be a natural choice to separate the equations, but then you still have to divide. Perhaps there is another transformation that can be applied, something between the simple logarithm and the Laplace/Fourier/etc transforms so useful in differential equations.

I'm aware of iterative methods to solve linear equations without computing $A^{-1}$. I'm looking for a pre-processing transformation (which might itself be very complicated!) to convert the equation into something trivially easy to solve (say, for a black box computer which only knows addition & subtraction), after which I can apply the inverse transformation to solve the original equation.

$\endgroup$
11
  • 4
    $\begingroup$ isn't that what the LU decomposition is supposed to achieve? $\endgroup$ Dec 10, 2019 at 16:46
  • 1
    $\begingroup$ LU decomposition converts a dense system to a triangular system, which is helpful, but the resulting equations using forward- and backward-substitution still require scalar division to solve. $\endgroup$ Dec 10, 2019 at 17:14
  • $\begingroup$ Could you expand on the "something trivially easy to solve" constraint? Are you specifically interested in a computer that can only use addition/subtraction, or more interested in the overall computational complexity of that step? $\endgroup$ Dec 10, 2019 at 18:58
  • 1
    $\begingroup$ "$A$ commutes with both $X$ and $C$" I guess $C$ is supposed to be $B$? $\endgroup$ Dec 13, 2019 at 22:57
  • 6
    $\begingroup$ May I remark that the equality $\log(AX) = \log(A)+\log(X)$ for commuting $A$ and $X$ seems to be much more subtle than the wording in your question suggests? Even in dimension $1$ this is only true (over the complex field) if we choose appropriate branches of the three logarithms in the formula. In more than one dimension we would have to choose branches of the three logarithms which work for all eigenvalues simultaneously. I'm not even sure whether this is always possible. $\endgroup$ Dec 14, 2019 at 2:08

2 Answers 2

0
$\begingroup$

Some definitions and comments on the logarithm of a nonsingular symmetric matrix. The set $\mathbb C\backslash\mathbb R_{-}$ is star-shaped with respect to 1, so that we can define the principal determination of the logarithm for $z\in \mathbb C\backslash\mathbb R_{-}$ by the formula \begin{equation} \text{Log}{z}=\oint_{[1,z]}\frac{d\zeta}{\zeta}. \end{equation} The function $\text{Log}$ is holomorphic on $\mathbb C\backslash\mathbb R_{-}$ and we have $\text{Log}z=\ln z$ for $z\in\mathbb R_{+}^*$ and by analytic continuation $e^{\text{Log} z}=z$ for $z\in\mathbb C\backslash\mathbb R_{-}$. We get also by analytic continuation, that $\text{Log}{e^z}=z$ for $\vert{\Im z}\vert<\pi$.

Let $\Upsilon_{+}$ be the set of symmetric nonsingular $n\times n$ matrices with complex entries and nonnegative real part. The set $\Upsilon_{+}$ is star-shaped with respect to $I$ (the identity matrix) (exercise). We can now define for $A\in\Upsilon_{+}$ \begin{equation} \text{Log} A=\int_{0}^1 (A-I)\bigl(I + t (A-I)\bigr)^{-1}dt. \tag 1\end{equation} We note that $A$ commutes with $(I+sA)$ (and thus with $\text{Log} A$), so that, we get that $ \forall A\in \Upsilon_{+}, \forall \theta >0,\ e^{\text{Log} (A+\theta I)}=(A+\theta I), $ and by continuity \begin{equation}\label{detlog} \forall A\in \Upsilon_{+}, \quad e^{\text{Log} A}=A,\quad \text{which implies}\quad \det A=e^{\text{trace} \text{Log} A }. \end{equation} Let me go back to your question about the matrix equation $AX=B$. Let me assume that $A\in \Upsilon_+$: then you get $$ X=e^{-\text{Log}A} B. $$ In other words, to calculate the inverse of $A$, you need only to calculate the logarithm of $A$. Also our assumption on $A$ can be relaxed: in fact it is enough to assume that the spectrum of $A$ does not intersect $(-\infty,0]$ and to replace the "segment" $[I,A]$ by a curve in the set of invertible matrices starting at $I$ and ending at $A$: that could be a simple way to prove that any invertible matrix is the exponential of another matrix, by the way a simpler way than the Jordan decomposition. Note that you can manage negative eigenvalues by changing the contour (except for this last point, the procedure above works in infinite dimension).

$\endgroup$
0
$\begingroup$

Maybe the transformation needed here is more trivial than expected. I'm thinking what the original question is looking for is simply the decomposition of the matrix equation to the collection of equations that are projections to each of its cartesian coordinates. This can be expanded in either the row or column vectors of the matrix. In details, for matrix $A$, the projection $T_i$ to $i$'th row has $\vec{T_i(A)} = \vec{A_i}$ (row vector of a matrix) and, by abuse of notation, $T_i(\vec{x}) = x_i$ (scalar coordinate), which would mean that to be consistent with linearity, for a product of matrix and vector, $\vec{T_i(A\vec{v})} = T_i(\vec{v})\vec{T_i(A)} = v_i\vec{A_i}$, which is a scalar product of a coordinate of the vector and a row vector from the matrix. Doing same transformation for both sides of the equation and repeating the process for all coordinate projections $T_i$ results in the canonical system of equations that the matrix equation represents. Solving this system of equations is still same than inverting $A$ though, but going from vector equation to (all of) its projections has similar simplifying power than taking logarithms has (matrices transform to vectors, vectors transform to scalars, matrix multiplication transforms to dot product of row vector with a column vector $T_{(i,j)}(AB) = T_i(\vec{T_j(AB)}) = \vec{T_i(A)} \cdot \vec{T_j(B^{\top})}$ , matrix multiplied by vector transforms to scalar product).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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