Search

Navigation

User login

Upcoming events

No upcoming events available

There are 497 members of the Warwick Mathematics Society, of which 0 are new today!
We're 99% of the way toward our target of 500 members.
You can join up on the UWSU website.

Who's new

weird matrix number thing

richardhp

Posted: Submitted by richardhp on 22 November 2007 - 11:26pm.

Joined: 2007-10-01
Posts: 167

cj showed me this today, basically you take any number and some multiples of it, if you then put these multiples as the columns of a matrix and take the determinant of that matrix, you get a multiple of the original number. eg, take n = 17 then two multiples 34 and 85. then the determinant of:
|3 8|
|4 5|

is -17, which is a multiple of 17. this seems to work for any number and 3 digit numbers and 3×3 matrices too. any ideas why this works?

Xedi

Posted: 23 November 2007 - 12:53am

Joined: 2007-10-03
Posts: 373

This post is decorative.

Xedi

Posted: 23 November 2007 - 12:58am

Joined: 2007-10-03
Posts: 373

Let α be a two digit number and let β and γ be your multiples : α=10φ+ψ, βα = 10a + b and γα=10c+d

$|A| = \left| \begin{array}{cc} a\quad c \\ b\quad d \end{array} \right| = ad - bc$

But αβγ=γ(βα)γ=β(γα)
So γ(10a+b) = β(10c+d)
Or d = γ/β(10a+b) - 10c
|A| = ad-bc = 10(γ/β)a^2 + (γ/β)ab -10ac -bc = (10a+b)(γ/β)a + (10a+b)(-c) = βα(γ/β)a + βα(-c) = α(aγ-βc)

This is a multiple of α.

In your case α=17 10a+b=βα=34 10c+d=γα=85
So a=3 γ=5 β=2 c=8
|A|= α(aγ-βc) = α(15-16) = -α = -17

Now I know this explanation is rubbish as it doesn't explain why it works, it just shows it's true for 2*2 matrices.
Ask the proof by induction guy for bigger matrices.

Edit : Well that went quite wrong. I made a silly mistake and then tried to correct it, thus giving two posts !

cosmin

Posted: 23 November 2007 - 1:04am

Joined: 2006-11-02
Posts: 1004

Yeah, I'm pretty sure this works in general as I've verified it with a 10 by 10 matrix and a five digit divisor last night. I'll get around to trying to prove it later I guess.

Sammy P 06

Posted: 1 December 2007 - 4:54pm

Joined: 2006-11-04
Posts: 53

I think this is a pretty solid proof:

Lemma. For an $n \times n$ matrix $A=(\alpha_{ij})$ , if we write the
cofactor of $\alpha_{ij}$ as $c_{ij}$ , then for $i \not = m$ we have

$\sum_{j=1}^n \alpha_{ij}c_{mj}\equiv 0$

Proof. I will introduce the notation $\zeta^{ab}_{cd}$ to mean the
determinant of the $(n-2)\times(n-2)$ matrix formed by disregarding
the $a$ -th and $b$ -th rows and the $c$ -th and $d$ -th columns of our
$n \times n$ matrix $A$ , for $a \not = b$ and $c \not = d$ . I will
use the notation from the MA106 lecture notes that $A_{ab}$ is the
$(n-1)\times(n-1)$ matrix obtained by disregarding the $a$ -th row
and $b$ -th column in $A$ .

Choose rows $i$ and $m$ with $i\not =m$ . The sum of the products of
$\alpha_{ij}$ and $c_{mj}$ is

$\sum_{r=1}^n\alpha_{ij}c_{mj} = \sum_{r=1}^n\alpha_{ij}(-1)^{i+j}|A_{mj}|$

In order to find a general expression for $|A_{mj}|$ we consider
several examples for $j$ . Choosing to expand $|A_{mj}|$ by the
$i$ -th row ( $i \not = m$ ) we see e.g.

$|A_{m1}|=\alpha_{i1}\zeta^{im}_{12}-\alpha_{i3}\zeta^{im}_{13}+\alpha_{i4}\zeta^{im}_{14}- \ldots \pm \alpha{in}\zeta^{im}_{1n}$

$|A_{m2}|=\alpha_{i1}\zeta^{i2}_{12}-\alpha_{i3}\zeta^{im}_{32}+\alpha_{i4}\zeta^{im}_{42}+\ldots \pm \alpha_{in}\zeta^{im}_{n2}$

$|A_{mn}|=\alpha_{i1}\zeta^{in}_{m1}-\alpha_{i2}\zeta^{in}_{m2}+\ldots\pm \alpha_{im}\zeta^{im}_{(n-1)n}$

So in general

$|A_{mj}|=(-1)^{1+1}\alpha_{i1}\zeta^{im}_{1j}+(-1)^{1+2}\alpha_{i2}\zeta^{im}_{2j} + \ldots + (-1)^{1+(j-1)}\alpha_{i(j-1)}\zeta^{im}_{j(j-1)} + (-1)^{1+j}\alpha_{i(j+1)}\zeta^{im}_{j(j+1)}+\ldots+(-1)^{n}\alpha_{in} \zeta^{im}_{jn}$

$|A_{mj}| = \sum_{k=1}^{j-1}(-1)^{k+1}\alpha_{ik}\zeta^{im}_{kj}+\sum_{k=j+1}^n(-1)^{k}\alpha_{ik}\zeta^{im}_{kj}$

$|A_{mj}| = \sum_{k=j+1}^n(-1)^{k}\alpha_{ik}\zeta^{im}_{kj} - \sum_{k=1}^{j-1}(-1)^{k}\alpha_{ik}\zeta^{im}_{kj}$

(where the left sum disappears if $j=1$ and the right sum disappears
if $j=1$ )

We multiply by $(-1)^{m+j}$ to give the cofactor $c_{mj}$ as

$c_{mj} = (-1)^{m+j}\left[ \sum_{k=1}^{j-1}(-1)^{k}\alpha_{ik}\zeta^{im}_{kj}-\sum_{k=j+1}^n(-1)^{k}\alpha_{ik}\zeta^{im}_{kj}\right]$

And then mutiplying by $\alpha_{ij}$ to give

$\alpha_{ij}c_{mj}= (-1)^{m+j}\left[\sum_{k=j+1}^n(-1)^{k}\alpha_{ij}\alpha_{ik}\zeta^{im}_{kj} - \sum_{k=1}^{j-1}(-1)^{k}\alpha_{ij}\alpha_{ik}\zeta^{im}_{kj} \right]$

We now show by induction that it is the case that the sum of the
first $\ell$ such terms is equal to

$\sum_{j=1}^{\ell}\alpha_{ij}c_{mj} = (-1)^m\sum_{k=\ell+1}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{\ell} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

which we call $P(\ell)$ .

For a base case we put $\ell = 1$ and see

$\sum_{j=1}^1 \alpha_{ij}c_{mj} = (-1)^m \sum_{k=2}^n (-1)^k \alpha_{ik} \left[ \sum_{r=1}^1 (-1)^r \alpha_{ir} \zeta^{im}_{rk} \right]$

$\alpha_{i1}c_{m1} = (-1)^{m+1}\sum_{k=2}^n (-1)^k \alpha_{ik} \alpha_{i1} \zeta^{im}_{1k}$

which agrees with the formula above for $\alpha_{ij}c_{mj}$ with
$j=1$ , so $P(1)$ holds.

To perform the inductive step we suppose by hypothesis $P(\ell)$ ,
i.e. that for the first $\ell$ terms,

$\sum_{j=1}^{\ell}\alpha_{ij}c_{mj} = (-1)^m\sum_{k=\ell+1}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{\ell} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

holds. If we take the $(\ell+1)$ -th term outside the sum we see this
is equal to

$(-1)^m\sum_{k=\ell+2}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{\ell} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right] + (-1)^{m+\ell+1}\alpha_{i(\ell+1)}\sum_{r=1}^\ell(-1)^r\alpha_{ir} \zeta^{im}_{r(\ell+1)}$

We then add the $(\ell + 1)$ -th term,

$\alpha_{i(\ell+1)}c_{m(\ell+1)} = (-1)^{m+\ell+1}\left[ \sum_{k=\ell+2}^n(-1)^{k}\alpha_{i(\ell+1)}\alpha_{ik}\zeta^{im}_{k(\ell+1)} -\sum_{k=1}^{\ell}(-1)^{k}\alpha_{i(\ell+1)}\alpha_{ik}\zeta^{im}_{k(\ell+1)}\right]$

Adding this to the sum of the first $\ell$ terms we see first of all
that

$(-1)^{m+\ell+1}\alpha_{i(\ell+1)}\sum_{r=1}^\ell(-1)^r\alpha_{ir} \zeta^{im}_{r(\ell+1)}$ cancels precisely with
$-(-1)^{m+\ell+1}\sum_{k=1}^{\ell}(-1)^{k}\alpha_{i(\ell+1)}\alpha_{ik}\zeta^{im}_{k(\ell+1)}$ so the sum of the first $(\ell + 1)$ terms can be written as

$\sum_{k=\ell + 2}^{n}\left[(-1)^{m+l+k+1} \alpha_{i(\ell +1)}\alpha_{ik}\zeta^{im}_{k(\ell+1)} + (-1)^{m+k} \alpha_{ik} \sum_{r = 1}^{\ell} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

$=(-1)^m\sum_{k=\ell+2}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{\ell+1} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

So $P(\ell) \implies P(\ell + 1)$ . Since $P(1)$ is true we have
$P(n)$ is true $\forall$ $n \in \mathbb{N}$ .

At this stage it is possible to simply `plug in' $\ell = n$ and see
the sum of all the $\alpha_{ij}c_{mj}$ is equal to

$\sum_{j=1}^{n}\alpha_{ij}c_{mj} = (-1)^m\sum_{k=n+1}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{n} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

which is a sum of zero terms and is therefore equal to 0. In case
this looks a bit suspect, we can sum the first $n-1$ terms to give

$\sum_{j=1}^{n-1}\alpha_{ij}c_{mj} = (-1)^m\sum_{k=n}^n(-1)^k \alpha_{ik} \left[ \sum_{r = 1}^{n-1} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

$= (-1)^m(-1)^n \alpha_{in} \left[ \sum_{r = 1}^{n-1} (-1)^r\alpha_{ir}\zeta^{im}_{rk}\right]$

$= (-1)^{m+n} \alpha_{in} \left[ \sum_{k = 1}^{n-1} (-1)^k\alpha_{ik}\zeta^{im}_{kn}\right]$

The $n$ -th term, $\alpha_{in}c_{mn}$ can be calculated as

$\alpha_{in}c_{mn}= (-1)^{m+n}\left[ - \sum_{k=1}^{j-1}(-1)^{k}\alpha_{ij}\alpha_{ik}\zeta^{im}_{kj} \right]$

$\alpha_{in}c_{mn}=-\sum_{j=1}^{n-1}\alpha_{ij}c_{mj}$ from which it
follows that

$\sum_{j=1}^{n}\alpha_{ij}c_{mj} = 0$ QED

Example: $n=4$ , $A = \left( \begin{array}{cccc}1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \\ 13 & 14 & 15 & 16 \end{array}\right)$

If we sum e.g. $\alpha_{2j}c_{1j}$ we see

$\sum_{j=1}^4 \alpha_{2j}c_{1j} = \left|\begin{array}{ccc} 6 & 7 & 8 \\ 10 & 11 & 12 \\ 14 & 15 & 16 \end{array}\right| - 2\left|\begin{array}{ccc} 5 & 7 & 8 \\ 9 & 11 & 12 \\ 13 & 15 & 16 \end{array}\right|+\ldots$

$= 6 \left|\begin{array}{cc}11 & 12 \\ 15 & 16 \end{array}\right| - 7\left|\begin{array}{cc}10 & 12 \\ 14 & 16 \end{array}\right| + \ldots = 0$

And it will always be the case that you only need to write the terms
as multiples of determinants of $(n-2)\times(n-2)$ matrices before
the terms cancel out. E.g. for a $100 \times 100$ matrix, you would
only need to do two lines of working to find
$\sum_{j=1}^{100}\alpha_{ij}c_{mj}$ in terms of a sum of $98 \times 98$ determinants, before every term precisely cancels without any
further working, which I think is pretty neat.

Now the:

Theorem. If $m \in \mathbb{Z}$ , and $k_1m, \ldots, k_n m$ are
$n$ -digit multiples of $m$ (where $k_i \in \mathbb{Z}$ , then the $n \times n$ matrix whose columns are the decimal digits of the $k_im$
has a determinant divisible by $m$ .

Proof. Write $A = (\alpha_{ij})$ . For each $j$ we have
$10^{n-1}\alpha_{1j}+10^{n-2}\alpha_{2j}+\ldots +10\alpha_{(n-1)j} + \alpha_{nj} = k_jm$ . We can rearrange this to write $\alpha_{nj} = k_jm - \sum_{i=1}^{n-1}10^{n-i}\alpha_{ij}$ .

We can expand the determinant of $A$ by the bottom row, so

$|A| = \sum_{j=1}^n \alpha_{nj}c_{nj}$

Substituting in our expression for $\alpha_{nj}$ from above:

$|A| = \sum_{j=1}^n c_{nj}\left[k_jm - \sum_{i=1}^{n-1}10^{n-i}\alpha_{ij}\right]$

$|A| = \sum_{j=1}^n c_{nj}k_jm - \sum_{j=1}^n\sum_{i=1}^{n-1}10^{n-i}\alpha_{ij}c_{nj}$

$|A| = m\sum_{j=1}^n c_{nj}k_j - \sum_{i=1}^{n-1}10^{n-i}\sum_{j=1}^{n}\alpha_{ij}c_{nj}$

By the above lemma, $\sum_{j=1}^{n}\alpha_{ij}c_{nj}$ since $i \not = n$ .

Since every element in the matrix is an integer, all the cofactors
will be integers. Therefore $\sum_{j=1}^n c_{nj}k_j$ is an integer.

Then we have

$|A| = m\underbrace{\sum_{j=1}^n c_{nj}k_j}_{integer} - \sum_{i=1}^{n-1}10^{n-i}\underbrace{\sum_{j=1}^{n}\alpha_{ij}c_{nj}}_{=0}$

$\frac{|A|}{m} = \sum_{j=1}^n c_{nj}k_j$

which is sums and integers multiples of integers, therefore it is an
integer.

Therefore $m|Det(A)$ . QED

Example: $m=87$ , $k_1=6$ $k_2=5$ , $k_3 = 11$

$A = \left(\begin{array}{ccc} 5 &4&9\\ 2&3&5\\ 2&5&7\end{array}\right)$

$= \left(\begin{array}{ccc} 5 &4&9\\ 2&3&5\\ 6\cdot87 - 100\cdot5 - 10\cdot 2&5\cdot87 - 100\cdot4 - 10\cdot3 &11\cdot87 - 100\cdot9 - 10\cdot5\end{array}\right)$ Find $Det(A)$
by expanding by the bottom row to give

$Det(A)=6\cdot87c_{31} - 100\cdot5c_{31} - 10\cdot 2c_{31} +5\cdot87c_{32} - 100\cdot4c_{32} - 10\cdot3c_{32}+ 11\cdot87c_{33} - 100\cdot 9 c_{33} - 10\cdot_5 c_{33}$

$Det(A) = 87(6c_{31}+5c_{32}+11c_{33})-100(5c_{31}+4c_{31}+9c_{33}) - 10(2c_{31}+3c_{32}+5c_{33})$

$Det(A) = 87\underbrace{(6c_{31}+5c_{32}+11c_{33})}_{\in\mathbb{Z}}-100\underbrace{(\alpha_{11}c_{31}+\alpha_{12}c_{32} + \alpha_{13}c_{33})}_{=0}-10\underbrace{(\alpha_{21}c_{31}+\alpha_{22}c_{32} + \alpha_{23}c_{33})}_{=0}$

Therefore $87|Det(A)$ .

Sorry I don't know how to do the matrices on the forum!

I won't pretend I didn't spend all of yesterday trying to prove that, and today writing it convincingly!

darthsteven

Posted: 1 December 2007 - 7:45pm

Joined: 2006-08-31
Posts: 694

You need to be an exec member to use & in posts I'm afraid, just a side effect of the way the website has to work.

cosmin

Posted: 2 December 2007 - 4:05am

Joined: 2006-11-02
Posts: 1004

Really? Why is that?

darthsteven

Posted: 2 December 2007 - 3:36pm

Joined: 2006-08-31
Posts: 694

I meant: to use a & in LaTeX.

You need to be an exec member do you can post things without having your posts go through the html filter. Essentially every post is stored in the DB verbatim. Then when it comes to render the page Drupal runs that input though an input format. You can define different input formats consisting of different input filters.

Input filters can do many things, one changes $\LaTeX$ stuff into images and table to make it look like $\LaTeX$ another makes urls into links, another sanitises HTML so nothing bad (like marquees) can be output by the site.

The default input format on the site, has four filters:

URL filter
HTML filter
DruTeX filter
Textile filter

And they are applied in that order, so: & is changed to & before it gets to the DruTeX filter, and I don't want to change the order of the filters, because I don't want to let some of the things that DruTeX outputs through the HTML filter if they didn't come from DruTeX.

Hope that clears things up, it does bug me though, if I could find a way I would get & working for $\LaTeX$

cosmin

Posted: 2 December 2007 - 8:26pm

Joined: 2006-11-02
Posts: 1004

Right, that makes sense, but how come it does it for me as well even though I'm exec ( $&$ )? I've noticed the full/filtered html and latex + textile stuff in the input format but I don't think there's a way for me to run the latex filters without running the html one.

darthsteven

Posted: 2 December 2007 - 10:08pm

Joined: 2006-08-31
Posts: 694

You'll want 'Unrestricted LaTeX + Textile', do you have that?

cosmin

Posted: 3 December 2007 - 1:53am

Joined: 2006-11-02
Posts: 1004

Nope, that's the thing, I only have "Filtered HTML", "Full HTML" and "LaTeX + Textile".

Smithers

Posted: 3 December 2007 - 7:26am

Joined: 2006-10-18
Posts: 26

Yeah < and > don't work in $\LaTeX$ either:
$<$ , $>$

Same reason: they get changed to & lt; and & gt;

Newtonswig

Posted: 3 December 2007 - 8:08pm

Joined: 2006-10-01
Posts: 427

Moving briefly away from the intricacies of the latex command line, Sammy's proof shows that there is nothing special about the decimal expansion in particular, meaning that this should work for numbers in any base. There is a general result in here, I'm sure of it. Something about homomorphisms of truncated polynomial rings...

...Algebra kids- make the magic happen!

Xedi

Posted: 4 December 2007 - 8:50pm

Joined: 2007-10-03
Posts: 373

Hey guys,
I think I got an explanation :
Let m be your original integer.
Take your matrix
$A= \left[\begin{array}{cccc} a_{11} \quad a_{12} \quad \hdots \quad a_{1n} \\ a_{21} \quad a_{22} \quad \hdots \quad a_{2n} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ a_{n1} \quad a_{n2} \quad \hdots \quad a_{nn}\\ \end{array}\right]$

with

$b^{n-1}\cdot a_{11}+ b^{n-2}\cdot a_{12}+\hdots +a_{1n}$

$b^{n-1}\cdot a_{21}+ b^{n-2}\cdot a_{22}+\hdots +a_{2n}$

$\vdots$

$b^{n-1}\cdot a_{n1}+ b^{n-2}\cdot a_{n2}+\hdots +a_{nn}$

all multiples of the original number m (where b is the base we're working in).

Take the matrix
$B= \left[\begin{array}{cccc} 1 \quad 0 \quad \hdots \quad b^{n-1} \\ 0 \quad 1 \quad \hdots \quad b^{n-2} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ 0 \quad 0 \quad \hdots \quad 1\\ \end{array}\right]$

Notice $|B| = 1$ as we have
$|B|= \left|\begin{array}{cccc} 1 \quad 0 \quad \hdots \quad b^{n-1} \\ 0 \quad 1 \quad \hdots \quad b^{n-2} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ 0 \quad 0 \quad \hdots \quad 1\\ \end{array}\right| = 1 \left|\begin{array}{cccc} 1 \quad 0 \quad \hdots \quad b^{n-2} \\ 0 \quad 1 \quad \hdots \quad b^{n-3} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ 0 \quad 0 \quad \hdots \quad 1\\ \end{array}\right| = 1 \left|\begin{array}{cccc} 1 \quad 0 \quad \hdots \quad b^{n-3} \\ 0 \quad 1 \quad \hdots \quad b^{n-4} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ 0 \quad 0 \quad \hdots \quad 1\\ \end{array}\right| = \hdots = \left|\begin{array}{cc} 1 \quad b \\ 0 \quad 1 \\ \end{array}\right| =1$

But

$AB = \left[\begin{array}{cccc} a_{11} \quad a_{12} \quad \hdots \quad a_{1n} \\ a_{21} \quad a_{22} \quad \hdots \quad a_{2n} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ a_{n1} \quad a_{n2} \quad \hdots \quad a_{nn}\\ \end{array}\right] \left[\begin{array}{cccc} 1 \quad 0 \quad \hdots \quad b^{n-1} \\ 0 \quad 1 \quad \hdots \quad b^{n-2} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ 0 \quad 0 \quad \hdots \quad 1\\ \end{array}\right] \\= \left[\begin{array}{cccc} a_{11} \quad a_{12} \quad \hdots \quad b^{n-1}\cdot a_{11}+ b^{n-2}\cdot a_{12}+\hdots +a_{1n} \\ a_{21} \quad a_{22} \quad \hdots \quad b^{n-1}\cdot a_{21}+ b^{n-2}\cdot a_{22}+\hdots +a_{2n} \\ \vdots \quad \vdots \quad \ddots \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \vdots \\ a_{n1} \quad a_{n2} \quad \hdots \quad b^{n-1}\cdot a_{n1}+ b^{n-2}\cdot a_{n2}+\hdots +a_{nn}\\ \end{array}\right]$

So in the last column of AB we've got our original integers.
As |B| = 1, |AB|=|A|.
Then all the numbers in the last column are multiple of our original number m.
But using the well known property of determinants that multiplying a row/column by x multiplies the determinant by x,
we have that |A| is a multiple of m, our original number ! $\square$

P.S. : That Matrix LaTeX typesetting is nasty without the &s.

darthsteven

Posted: 4 December 2007 - 9:08pm

Joined: 2006-08-31
Posts: 694

I'd rather make a it look nasty than have a huge open security hole. If you want to fix the issue, join the website team, and I'll give you access to the code.