# any pattern here ? (revised 2)

for any positive number $k$, I have a $(k+1)*(k+1)$ matrix. I wonder if these matrices follow any "obvious" pattern. My goal is to guess the elements for matrix with $k=5$ and above (most probably in a recursive way, and using some combinatorial functions)

$$k=1, \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix}$$

$$k=2, \begin{bmatrix} 2& 2& 2\\ 2& 0& -2\\ 2& -2& 2 \end{bmatrix}$$

$$k=3, \begin{bmatrix} 3& 3& 3& 3\\ 3& 1& -1& -3\\ 3& -1& -1& 3\\ 3& -3& 3& -3 \end{bmatrix}$$

$$k=4, \begin{bmatrix} 6& 6& 6& 6& 6\\ 6& 3& 0& -3& -6\\ 6& 0& -2& 0& 6\\ 6& -3& 0& 3& -6\\ 6& -6& 6& -6& 6 \end{bmatrix}$$

Any of the above matrices may be multiplied by an arbitrary constant (for example the top-left element of each matrix) to normalize.

any guess or comment is appreciated.

EDIT: here is how I derived these: see here for definitions. given the eigen decomposition $AA^{T}=Q \Lambda Q^{T}$, we define $W=A^{T} Q \Lambda^{-1}Q^{T}$, considering the symmetry, if the kmer $u_j$ and gapped-kmer $v_i$ have $m$ mismatches, then $w_{j,i}=w_m$. Hence to find $W$, we only need to find {$w_0,...,w_k$}. I guess that $w_m$ can be written as following ($c_0$ is a constant):
$$w_m = c_0\sum_{l=0}^k \alpha_{k,m,l} \binom{L}{l}$$ for $k=1,2,3,4$ and $m=0,1,..,k$ and $l=0,1,..,k$, I have numerically calculated the value for $\alpha_{k,m,l}$, which is given as the above matrices. The question is what $\alpha_{k,m,l}$ is for general k.

EDIT: also see here for a solution to eigen decomposition by Siva.

EDIT: with a few reasonable assumptions, I have found a common pattern and made an R code that generates these matrices recursively. Following are few more matrices generated by my program (unlike the above four matrices, the following are neither proven nor tested to be the solution for the above $\alpha_{k,m,l}$ equation:

$$k=5, \begin{bmatrix} 10& 10& 10& 10& 10& 10\\ 10& 6& 2& -2& -6& -10\\ 10& 2& -2& -2& 2& 10\\ 10& -2& -2& 2& 2& -10\\ 10& -6& 2& 2& -6& 10\\ 10& -10& 10& -10& 10& -10 \end{bmatrix}$$

$$k=6, \begin{bmatrix} 15& 15 & 15& 15 &15 &15 &15\\ 15 & 10 & 5 & 0 & -5& -10 & -15\\ 15 & 5 & -1 & -3 & -1 & 5 & 15\\ 15 & 0 &-3 & 0 & 3 & 0 & -15\\ 15 & -5 & -1 & 3 & -1 &-5 & 15\\ 15 & -10 & 5 & 0 & -5 & 10 & -15\\ 15 &-15& 15 &-15& 15 &-15& 15 \end{bmatrix}$$

Again the scales are arbitrary.

EDIT: We recently found a solution for $w(m)$ as following: $$w_m=\frac{(-1)^{m}}{2^{L}\binom{L}{k-m}}\frac{L-k}{L-k+m}\sum_{t=0}^{k-m}\binom{L}{t} =\frac{{k-L \choose m}}{2^{L}\binom{L}{k} \binom{k}{m}} \sum_{t=0}^{k-m}\binom{L}{t}$$ For interested readers, this solution is described in Robust k-mer frequency estimation using gapped k-mers.

Now, having this result how can one solve for $\alpha_{k,m,l}$ in $w_m = c_0\sum_{l=0}^k \alpha_{k,m,l} \binom{L}{l}$? Note that here $c_0$ may depend on $k$ and $L$ but not $m$ or $l$. My guess is that $c_0^{-1}=2^L\binom{L}{k}$. Also $\alpha_{k,m,l}$ is a function of $k,m$ and $l$ and most likely symmetric in $l$ and $m$ as the above examples suggest.

-
Needs context. Where did you get these amtrices? How you arrived at this. – user1708 Apr 12 '11 at 12:33
If you can calculate this for a specific k, why can't you use the same calculation for a general k? – configurator Apr 12 '11 at 15:31
What do you mean by $\Lambda ^{-1}$? Aren't some of the eigenvalues zero? – Siva Apr 13 '11 at 15:32
@Siva: I only take the nonzero eigenvalues and their corresponding eigencevtors. so that $Q$ is an $M*r$ (the columns of $Q$ are the eigenvectors for $AA^{T}$) and $\Lambda$ is a diagonal $r*r$ matrix, where $r=rank(AA^{T})$ and $M$=number of gapped k-mers. – mghandi Apr 13 '11 at 16:30

I see finite difference representations of derivatives. http://mathworld.wolfram.com/FiniteDifference.html

As an engineering-type, I think Wolfram does a crappy job for it.

I prefer a numerical methods text with good tables. http://amzn.com/0072431938 Try up in the 630's. 626 perhaps? I'm doing this from memory.

Proper derivation is done using sums of Taylor series approximations to the function.

Aha. Less bad. https://reference.wolfram.com/mathematica/tutorial/NDSolvePDE.html Check out the large table about 10% down the page.

-

You can also use matlab for this type of questions. And yes the proper derivation is done using sums of Taylor series.

-