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.

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.

share|improve this question
3  
Needs context. Where did you get these amtrices? How you arrived at this. –  user1708 Apr 12 '11 at 12:33
4  
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
add comment

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.