10
$\begingroup$

Generate a $5 × 5$ matrix such that the each entry is an integer between $1$ and $9$, inclusive, and whose determinant is divisible by $271$.

This is a practice problem for a linear algebra exam I have coming up, and can't for the life of me figure it out. I was thinking maybe making a triangular matrix ($0$s below main diagonal, determinant would be the product of the diagonal), but that wouldn't work because it says to use integers $1$-$9$.

Been thinking of this problem all day. The only way we've covered the determinant for a large matrix ($3 × 3$ or larger) has been through summing up the signed elementary product, but for a $5 × 5$ matrix, you'd need to make sure that all $5! = 120$ signed elementary products would need to be divisible by $271$.

If anyone has a better way to approach and solve this problem, it would be very much appreciated.

$\endgroup$
  • $\begingroup$ $271$ is prime so the elementary products cannot be divisible by $271$, being one of $1, 2, \ldots, 9$. $\endgroup$ – mechanodroid Feb 28 '18 at 0:04
  • 10
    $\begingroup$ If you make all the entries 1, then the determinant is 0 which is divisible by 271. $\endgroup$ – Daniel Schepler Feb 28 '18 at 0:10
  • 2
    $\begingroup$ Multiply 271 by a number (maybe 211) getting 57181. Multiply 271 by another number giving also a 5 digit number. Do this 3 more times. For the first line of your matrix, take the digits of the first result in the order you have them. Same thing for 2nd, 3rd, 4th and 5th row. The determinant will be divisible by 271. Have fun finding out why this works. Fifty years ago, I had this problem in an exam and I still remember it... $\endgroup$ – Bernard Massé Feb 28 '18 at 1:03
  • 2
    $\begingroup$ Oh I get it. Multiply first column by 10, add to second column, multiply that result by 10, add to third column, ... . Incidentally, you can use 1 1 1 1 1 on any row by this method (271×41). $\endgroup$ – Oscar Lanzi Feb 28 '18 at 2:25
  • 1
    $\begingroup$ @legionary I managed to get exactly $271$. You can read my answer below. $\endgroup$ – астон вілла олоф мэллбэрг Feb 28 '18 at 4:11
7
$\begingroup$

Let $\overline{a_{i1}a_{i2}a_{i3}a_{i4}a_{i5}}$, $i \leq 1 \leq 5$ be five distinct five digit multiples of $271$ which have non-zero digits. We claim that the matrix $a_{ij}$ has a determinant divisible by $271$. That is, if we have the matrix whose rows are the multiples of $271$, then it has a determinant divisible by $271$.

The proof is rather clever, really : note that determinants are preserved under column addition and subtraction operations. Therefore, if $C_i$ are the columns, perform $C_5 \to 10000C_1 + 1000C_2 + 100C_3 + 10C_4 + C_5$. Performing this, the determinant does not change, but now, $(C_5)_j = 10^4 a_{j1} + 10^3 a_{j2} + .. = \overline{a_{j1} a_{j2}...a_{j5}}$, for all $1 \leq j \leq 5$. Hence, the column $C_5$ consists completely of multiples of $271$. By multilinearity of the determinant, it follows that the determinant of the matrix is divisible by $271$.

I am sure that you can easily find five multiples of $271$ which satisfy the situation, and furthermore give a non-zero determinant, divisible by $271$.

Take these multiples : $99728,98915,66666,31436,48238$, and form the matrix: $$ \begin{pmatrix} 9\quad 9 \quad 7 \quad 2 \quad 8 \\ 9 \quad 8 \quad 9 \quad 1 \quad 5 \\ 6 \quad 6 \quad 6 \quad 6 \quad 6 \\ 3 \quad 1 \quad 4 \quad 3 \quad 6 \\ 4 \quad 8 \quad 2 \quad 3\quad 8\\ \end{pmatrix} $$ which has determinant $-1626 = 271 \times -6$. Interestingly enough, if you write $11111$ above instead of $66666$, and swap two rows, you will get exactly $271$ as the determinant.

$\endgroup$
  • 1
    $\begingroup$ Is it on purpose you used $C_2$ twice in your sum for $C_4$? $\endgroup$ – qwr Feb 28 '18 at 6:13
  • $\begingroup$ Wow, thanks a bunch. $\endgroup$ – legionary Feb 28 '18 at 8:34
  • 1
    $\begingroup$ @qwr It was an error in writing. You may see the edited version. Also, you are welcome, legionary. $\endgroup$ – астон вілла олоф мэллбэрг Mar 1 '18 at 22:52
  • $\begingroup$ @legionary Worth adding that the "interestingly enough" example also answers Ethan Bolker's question from below of a matrix which uses all digits at least once, but has determinant equal to $271$. $\endgroup$ – астон вілла олоф мэллбэрг Mar 1 '18 at 23:10
  • 1
    $\begingroup$ @астонвіллаолофмэллбэрг Also, is $(C_4)_j$ supposed to be $5$? I don't think this proof is cheap at all; I think it's quite clever. $\endgroup$ – qwr Mar 2 '18 at 5:03
5
$\begingroup$

If you make all the entries $1$, then the determinant is $0$, which is divisible by $271$.

courtesy of @ Daniel Schepler

$\endgroup$
  • 2
    $\begingroup$ This is correct and clever. I wonder if it's what the questioner had in mind. If so the information about the digits is deliberately confusing. That makes for a clever problem, but I don't think clever problems belong on exams. For fun: can you find a solution that uses each digit at least once? $\endgroup$ – Ethan Bolker Feb 28 '18 at 0:29
  • $\begingroup$ I disagree about clever problems on exams. They test your ability to think outside the box. If you know some chemistry try this. $\endgroup$ – Oscar Lanzi Feb 28 '18 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.