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.

Let 'M' be an $(a-1)\times(a-1)$ coeifficent matrix, $\large\ m_{r,c}=\left\{\Large\frac{r\cdot c}{a}\right\}$

Where $\{ x \}$ is the fractional part of $x$.

And let vectors 'G' and 'H' be column vectors, $\vec{G}=\begin{bmatrix} j_1 \\ j_2 \\ j_3 \\: \\ : \\ j_{a-1}\end{bmatrix}$, $ \vec{H}=\begin{bmatrix} y_1 \\ y_2 \\y_3 \\ : \\ : \\ y_{a-1} \end{bmatrix}$,

Does M$\vec{G}=\vec{H}$, always have a unique solution for any integer a>3, if so prove it please

share|improve this question
    
I believe that EuYu is correct about singularity, however considering your function f(k,a,b) from your other related question, if you want to do non-zero for $k \equiv \pm b \mod{a}$, it may be possible. For example, for $a=5$ use $f=3\{\frac{k}{5}\} +\{\frac{2k}{5}\}-\{\frac{3k}{5}\}-3\{\frac{4k}{5}\}$ (coefficients of 3,1,-1,-3) which is non-zero only for $1$ and $4 \equiv -1$ –  adam W Nov 30 '12 at 21:55
    
Could you explain more, I could open another bounty if you show me what you mean. –  Ethan Dec 3 '12 at 3:30
    
Well, I suppose that then you may be interested in such a multiple selection...but it would depend on the rank of the matrix. For the $a=5$ example, the rank is $4$, which means any two non-zero could be found. For the higher dimensions, it may not be so easy, for example if the rank for $a=30$ (for example, I did not evaluate) is $20$, then a function with $11$ non zero might be discernible. Think of Gaussian reduction and zeroing the desired elements, and how the options for reducing remain so long as there is span/rank to work with. –  adam W Dec 6 '12 at 3:10
add comment

1 Answer 1

up vote 2 down vote accepted
+100

Not a truly complete answer but too long for a comment.

The short answer is no, your matrix will not have a unique solution for all $a > 3$. I cannot completely classify invertibility of these matrices in terms of $a$, but let me write what I have so far.

Note that your matrix $M$ is given by the difference $M=A - B$.

The matrix $A$ is the $(a-1) \times (a-1)$ "multiplication table" scaled by $a^{-1}$. For $a=5$ we have $$A=\frac{1}{5}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 9 & 12 \\ 4 & 8 & 12 & 16\end{pmatrix}$$ Note that this matrix has rank $1$.

$B$ is the matrix of integer parts, i.e. $b_{ij} = \left\lfloor\frac{ij}{a}\right\rfloor$. The companion $B$ to the above $A$ is given as $$B=\begin{pmatrix}0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 2\\0 & 1 & 2 & 3\end{pmatrix}$$ Notice that this $B$ has $\mathbf{b_4} = \mathbf{b_2} + \mathbf{b_3}$ where $\mathbf{b_i}$ denotes the corresponding row vectors of $B$. Therefore this matrix has rank $2$. Now note that rank is sub-additive so $$\operatorname{rank}(M) = \operatorname{rank}(A-B) \le \operatorname{rank}(A) + \operatorname{rank}(B) \le 3$$ Therefore we have shown that your matrix for $a=5$ is non-invertible. Hence the solution will not be unique or even necessarily consistent. We can actually say a bit more.

The rowspace of $A$ is spanned by the vector $\begin{pmatrix}1 & 2 & \cdots & a-1\end{pmatrix}^\mathrm{T}$ while the rowspace of $B$ is always zero for the first entry. This means that the rowspace (and consequently columnspace) of the matrices are disjoint. It is a rather well known result that the rank sub-additivity reaches equality for matrices with disjoint column and rowspaces and therefore we actually have $$\operatorname{rank}(M) = \operatorname{rank}(A) + \operatorname{rank}(B)$$

You will have a unique solution if and only if $B$ as defined above has rank $a-2$.

This of course does not answer your question, but it is (perhaps) a cleaner criterion for checking invertibility since $B$ has integer entries. With this result, similar methods as above will easily show that the matrix is invertible for $a = 3$ and $4$.

Numerically, I have tested these matrices for $a \le 1000$. The only results for which the matrix is invertible is $a=3,\ 4,\ 6$. This is somewhat to be expected since we except at least some sort of linear dependency between the non-zero rows of $B$ as the number of rows increase. Numerically, the rank of the matrix tends to hover around $\frac{a}{2}$.

I would conjecture that your matrix is singular for all values of $a$ except $3,\ 4$ and $6$ but I cannot prove it. Perhaps someone else can take over from here.

share|improve this answer
    
I am very greatful for all the time you spent in helping me with this, though the fact that the matrix is singular for even a single value greater then 3, already defeats what I was attempting do, my original problem was this ( math.stackexchange.com/questions/244648/function-expansion-help ) if you could help me out a little with this problem, I would gladly give you the bounty, here. –  Ethan Nov 28 '12 at 9:33
    
From what I can tell on the other question, this basically boils down to solving the matrix equation $M\mathbf{x} = \mathbf{e_1}$ where $\mathf{e_1}$ is the first standard basis vector. This system is not always consistent. For example, for $a=5$, there will be no solution. –  EuYu Nov 28 '12 at 18:50
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.