TITLE: Inequality involving traces and Toeplitz matrices
QUESTION [2 upvotes]: Suppose that I have $n\times n$ matrices $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{B}_{\epsilon}$ that are real with non-negative entries. The following properties hold for these matrices:

$\mathbf{A}$ is a symmetric Toeplitz matrix.
Denote by $a_d$ the entries in the diagonal $d$ away from the main (central) diagonal.
For some constant $T<n$, the entries $a_t=0$ for all $t\geq T$ and
$a_t>0$ for all $t<T$.  Thus, $\mathbf{A}$ has the following form:
$$\mathbf{A}=\overbrace{\left.\left[\begin{array}{11c}
   a_1&a_2&a_3&\cdots&a_t&0&0&\cdots&0&0&0\\
   a_2&a_1&a_3&\cdots&a_{t-1}&a_t&0&\cdots&0&0&0\\
   a_3&a_2&a_1&\cdots&a_{t-2}&a_{t-1}&a_t&\cdots&0&0&0\\
   &\vdots&&&&&&&&\vdots&\\
   0&0&0&\cdots&a_{t}&a_{t-1}&a_{t-2}&\cdots&a_1&a_2&a_3\\
   0&0&0&\cdots&0&a_t&a_{t-1}&\cdots&a_2&a_1&a_2\\
   0&0&0&\cdots&0&0&a_t&\cdots&a_3&a_2&a_1\\
   \end{array}\right]\right\}}^nn$$
(in my problem, $\mathbf{A}$ is a covariance matrix.)
$\mathbf{B}$ is a diagonal matrix with entries equal to $b>0$:  $\mathbf{B}=b\mathbf{I}$, where $\mathbf{I}$ is the identity matrix.
$\mathbf{B}_{\epsilon}$ is a diagonal matrix defined as follows: given constants $\epsilon_0$ and $\epsilon_1$ such that $0<\epsilon_0<b$ and $\epsilon_0<\epsilon_1$, set two arbitrary entries $B_\epsilon[i,i]$ and $B_\epsilon[j,j]$ ($i\neq j$) in the diagonal of $\mathbf{B}_{\epsilon}$ to $b-\epsilon_0$ and $b+\epsilon_1$, and set the rest of the diagonal entries to $b$.
$\mathbf{A}+\mathbf{B}$ and $\mathbf{A}+\mathbf{B}_\epsilon$ are invertible.

I am interested in finding out whether asymptotically with $n\rightarrow\infty$ for constant $T$, $\epsilon_0$ and $\epsilon_1$ and the listed conditions:
$$\operatorname{Tr}[\mathbf{A}(\mathbf{A}+\mathbf{B})^{-1}\mathbf{A}]\geq\operatorname{Tr}[\mathbf{A}(\mathbf{A}+\mathbf{B}_{\epsilon})^{-1}\mathbf{A}]$$
where $\operatorname{Tr}[\mathbf{M}]$ denotes the trace of the matrix $\mathbf{M}$.
I have a hunch that it's true and that there exists $n_0$ such that for all $n>n_0$ the statement above is true.  This hunch is based on the fact that $\operatorname{Tr}[\mathbf{A}+\mathbf{B}]\leq\operatorname{Tr}[\mathbf{A}+\mathbf{B}_\epsilon]$ and that we are "dividing" by that (I know that the trace of the product is not the product of the trace, hence "dividing" in quotations).  However, my knowledge of linear algebra is not sufficient to prove this and my hunch may be wrong.  Any help would be appreciated.

REPLY [1 votes]: In the simplest example, your condition fails: let $A=I$, $b=1$, $\epsilon_1\in[0,1]$, $\epsilon_0=\epsilon_1/2$. Then $A+B=2I$, so
$$
\operatorname{Tr}(A(A+B)^{-1}A)=\frac{n}2.
$$
Also,
$$
\operatorname{Tr}(A(A+B_\epsilon)^{-1}A)=\frac{n-2}2+\frac1{2-\epsilon_0}+\frac1{2+\epsilon_1}.
$$
So
\begin{eqnarray}
\operatorname{Tr}(A(A+B)^{-1}A)-\operatorname{Tr}(A(A+B_\epsilon)^{-1}A)&=&-1+\frac1{2-\epsilon_0}+\frac1{2+\epsilon_1}=-1+\frac{4+\epsilon_1/2}{4+\epsilon_1-\epsilon_1^2/2}\\
&=&-\frac{\epsilon_1/2-\epsilon^2/2}{4+\epsilon_1-\epsilon_1^2/2}<0
\end{eqnarray}


TITLE: convergence of iteration method
QUESTION [0 upvotes]: Given the linear equation system;
$\begin{bmatrix}
  A_1 & B\\
  B^T & A_2
 \end{bmatrix}$$\begin{bmatrix}
  x_1 \\
  x_2
 \end{bmatrix}$=$\begin{bmatrix}
  b_1 \\
  b_2
 \end{bmatrix}$
where $A_1 \in \mathbb{R}^{n_1\times n_1} $,$A_2 \in \mathbb{R}^{n_2\times n_2}$ and $B\in \mathbb{R}^{n_1\times n_2}$, I've got to find the condition for convergence of followig iteration method:
$(1)$ $A_1x_1^{(k+1)}+Bx_2^{(k)}=b_1$
$(2)$ $B^Tx_1^{(k)}+A_2x_2^{(k+1)}=b_2$
I've brought the two equations together:
(1) $x_1^{(k+1)}=A_1^{-1}(b_1-Bx_2^{(k)})$
(2) $x_2^{(k+1)}=A_2^{-1}(b_2-B^Tx_1^{(k)})$ $\rightarrow$ $x_2^{(k)}=A_2^{-1}(b_2-B^Tx_1^{(k-1)})$
i.e.
$\rightarrow$ (1) $x_1^{(k+1)}=A_1^{-1}(b_1-BA_2^{-1}(b_2-B^Tx_1^{(k-1)}))$
Is it all in order? My question is how to apply  the theorem of convergence
for iteration methods, where the spectral radius of the iteration matrix has to be less one?

REPLY [2 votes]: The matrix of the linear part of the last equation is $$A_1^{-1}BA_2^{-1}B^T,$$ this has to be contractive for the method to work.


TITLE: $f(1+\frac{1}{n})=1$ for all integers $n$ , then find $f"(1)$
QUESTION [2 upvotes]: Let $f:\mathbb{R} \rightarrow \mathbb{R} $ be a non-constant, three times differentiable function. If $f(1+\frac{1}{n})=1$ for all integers $n$, then find $f''(1)$.

I could find $f'(1)=\lim_{n \rightarrow \infty} \frac{f(1+\frac{1}{n})-f(1)}{\frac{1}{n}}$.
Now, $f(1)=1$ due to continuity of $f$ at $1$.
But the expression of $f''(1)$ is becoming overtly complicated.
Please help.

REPLY [5 votes]: Observe that since we know that $\;f''(1)\;$ exists,  for $\;n\in\Bbb N\;$ , we have that (use for example Check my workings: Show that $\lim_{h\to0}\frac{f(x+h)-2f(x)+f(x-h)}{h^2}=f''(x)$)
$$f''(1)=\lim_{n\to\infty}\frac{f\left(1+\frac1n\right)-2f(1)+f\left(1-\frac1n\right)}{\left(\frac1n\right)^2}=\lim_{n\to\infty}\frac{1-2+1}{\frac1{n^2}}=0$$
Because, as you say, by continuity $\;f(1)=1\;$ .
Warning: One equality sign before the last one I am not passing to the limit in the numerator while keeping the denominator as it is. This would require justification. What I'm doing is substituting the actual values of $\;f\;$ at those points!


TITLE: $X$, find $A$ such that $A^m=X$
QUESTION [3 upvotes]: I encountered a problem as folows:
Show a    $3\times 3$ real matrx $A$, such that
$$A^4=\left(\begin{array}{ccc}3&0&0\\0&3&1\\0&0&0\end{array}\right)$$
well, this problem is not difficult, one can first find  $B=\left(\begin{array}{ccc}\sqrt3&0&0\\0&\sqrt3&x\\0&0&0\end{array}\right)$ such that $B^2=\left(\begin{array}{ccc}3&0&0\\0&3&1\\0&0&0\end{array}\right)$.
My problem is:

Let $m,n$ be two positive integers. then, for what  $n\times n$ real  matrix $X$, there exist real matrix $A$ such that $A^m=X$? Is there a general method or theorem to calculate all the matrices $X$ and $A$?

Maybe, there does not exist a  general answer. then, How about $n=3$ or $4$?
Thanks a lot!

REPLY [2 votes]: If you're working over $\mathbb{C}$, then everything boils down to the Jordan canonical form. I actually needed to look this up a while ago and there's a very good paper on the topic that is completely elementary (needs only knowledge of the Jordan canonical form):
http://www.math.technion.ac.il/iic/ela/ela-articles/articles/vol9_pp32-41.pdf

REPLY [1 votes]: Decompose $\mathbb{C}^n$ into generalized eigenspaces. Then if you find such an X for each eigenspace, you can combine them together to give an X for $\mathbb{C}^n$.
Therefore we can assume that $\mathbb{C}^n$ is a generalized eigenspace. Then we can choose a basis so that the matrix will be upper triangular. If the eigenvalue is non-zero, it will be simple to find such a matrix, one row at a time, starting from the bottom.
The generalized eigenspace for 0 is more complicated, and X might not exist.
So a partial answer is that if the matrix is invertible, X will always exist.


text:
\section{Problem Setup} \label{sec:setup}
We are interested in studying the following differential equation with stochastic parameters.

\begin{equation}
\label{eq:ode}
\frac{d}{dt}\x(t, \omega)=\f(\x, \aalpha(t, \omega)), \quad \x(0)=\x_0,
\end{equation}
where $\x \in \R^d$ are sate variables with coordinates
$(x_1, x_2, \ldots, x_d)$ and $\aalpha(\omega)\in \R^l$ are time-dependent random parameters with coordinates $(\alpha_1(t, \omega), \alpha_2(t, \omega),\ldots, \alpha_l(t, \omega))$.
We further assume that each state variable $x_i(t, \omega)\in [a_i, b_i]$ and each random parameter is contained in $[p_i, q_i]$ for any $t$ and $\omega$. For the random parameters, we assume they are piecewise constant in time and each parameter $\alpha_i(t, \omega)$ can be parameterized by a sequence of random vectors $(\Delta_i, a_i)$, where $\Delta_i\sim U(0, \Delta)$ and $a_i\sim U(0, a)$. If we define
\begin{equation*}
	t_n=\sum_{i=1}^n \Delta_i
\end{equation*}
then the random parameter $\alpha_i(t,\omega)=a_n$ if $t_n\leq t< t_{n+1}$.
We are interested in quantifying the uncertainty in the solution $\x(T, \Delta_1, a_1, \Delta_2, a_2, \ldots, \Delta_N, a_N)$ for $T>0$.

config: arxiv


TITLE: bit strings recurrence
QUESTION [0 upvotes]: Let $f(n)$ denote the number of bit strings. (Words from the alphabet $\{0,1\}$) of length $n$ which do not contain three consecutive zeros. How would you write a linear recurrence of order 3 with adequate initial conditions for $f(n)$.
Also need to verify it gives the correct answer for $n = 6$. How would you approach this ?

REPLY [1 votes]: see f(1) = 2, f(2) = 4 and f(3) = 7. from n$\geq$4 onwards, we have to think. Hmm..
f(n-1) might not have any zeros at the end of it, or one zero at the end, or two zeros at the end. Depending on that we can do certain things to each of them and that should give you a recurrence relation.
For example, if f(n-1) has no zeros at the end then we can either append a 0 or 1 at the end and get two times the string given by the f(n-1).
for other two, you can do adjustments accordingly and reach a recurrence involving three terms.


TITLE: second directional derivative in a volume
QUESTION [1 upvotes]: Having computed the gradient in a discrete volume data set with the help of central differences, I now want to compute the second directional derivative (in direction of the gradient). So as I understand it, this should be the curvature of an isosurface.
Can I do it like this? (pseudo code)
gradX=(value(x-1,y,z)-value(x+1,y,z))/2
gradY=(value(x,y-1,z)-value(x,y+1,z))/2
gradZ=(value(x,y,z-1)-value(x,y,z+1))/2

scndDerX=(gradLength(x-1,y,z)-gradLength(x+1,y,z))/2
scndDerY=(gradLength(x,y-1,z)-gradLength(x,y+1,z))/2
scndDerZ=(gradLength(x,y,z-1)-gradLength(x,y,z+1))/2

grad.normalize();

scndDer.dot(grad);
curvature=scndDer.length;

I'm trying to visualize it, and it just doesn't look quite correct. Therefor I just want to check if the math is alright.

REPLY [1 votes]: I have just looked up the definition of the second derivative here. According to this document, the $x, y$ and $z$ components must each be defined based on the entire first derivative. You have only defined each component in your second derivative based on the respective component in the first derivative. For example, the $x$ component of the second derivative will be $$\frac{\partial(f_x\, \mathbf{i} + f_y\,\mathbf{j}+ f_z \, \mathbf k)}{\partial x}\mathbf i$$
Here, I am expressing the function as $f$, and the subscript $_x$ or $_y$ or $_z$ indicates to take the derivative of $f$ with respect to that variable. Since $f$ is a function in three dimensions, I have defined it as a vector function. The unit vector in the $x$ direction is denoted $\mathbf i$ (a vector of length $1$), the unit vector in the $y$ direction is $\mathbf j$ and the unit vector for $z$ is $\mathbf{k}$. The $\partial$ sign indicates that we are treating all the $y$'s and $z$'s as constant as we differentiate (in this case) by $x$. Thus, you can see in the above formula that the first derivative (in the numerator: $f_x\, \mathbf{i} + f_y\,\mathbf{j}+ f_z \, \mathbf k$) is a sum of the derivatives of the function in each of these directions - which is the same as what you stated above. However, where you went wrong is to assume that the second derivative of, for example, the $x$ component is $f_{xx}\mathbf i$, where the double $_{xx}$ denotes taking the derivative with respect to $x$ twice. Once you do the $y$ and $z$ components of the second derivative, the final formula will look like:
$$\nabla \nabla f=\frac{\partial(f_x\, \mathbf{i} + f_y\,\mathbf{j}+ f_z \, \mathbf k)}{\partial x}\mathbf i+\frac{\partial(f_x\, \mathbf{i} + f_y\,\mathbf{j}+ f_z \, \mathbf k)}{\partial y}\mathbf j+\frac{\partial(f_x\, \mathbf{i} + f_y\,\mathbf{j}+ f_z \, \mathbf k)}{\partial z}\mathbf k$$