# Simple matrix help

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

-
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

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.

-
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