ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 24 Feb 2021 15:17:19 +0100How one can find a matrix with given condition?https://ask.sagemath.org/question/55877/how-one-can-find-a-matrix-with-given-condition/I found the following recreational mathematics problem too hard for me. Can anyone give me hints how to find a solution?
Consider a $4\times 4$ matrix with integer coefficients. Let its elements be $a_{i,j}$ for $1\leq i,j\leq 4$. Now form four sets $A_1$, $A_2$, $A_3$, $A_4$. Say that $A_1$ is the set of elements $a_{i,j}$. Also, $A_2$ is the set of elements $a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1}$ i.e. the set of sums of elements of $2\times 2$-subsquares of the matrix. Similarly, denote by $A_3$ the set of sums of $3\times 3$-submatrices and $A_4$ the set containing the sum of all elements of the given $4\times 4$-matrix.
Now, I heard a rumor that one can give an example of 16 integers $a_{i,j}$ such that all integers from 1 to 25 belong to $A_1 \cup A_2 \cup A_3 \cup A_4$. How can one find such an example? It is easy to see that at least some of the elements $a_{i,j}$ must satisfy $1\leq a_{i,j}\leq 25$ but there are still so many elements that finding such a matrix by brute force seems impossible. I was wondering if genetic algorithms or simulated annealing work for such a problem but I don't have enough experience to implement that.
The best I know is that getting all integers from 1 to 24 is possible, for instance using the matrix:
-42 22 23 7
13 11 -32 14
-23 16 15 8
19 9 -22 1Jaakko SeppäläWed, 24 Feb 2021 15:17:19 +0100https://ask.sagemath.org/question/55877/Speeding up matrix multiplication?https://ask.sagemath.org/question/8438/speeding-up-matrix-multiplication/I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a vector $v$, both with integral entries.
More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix and am interested in quickly computing the product $M \cdot v$ modulo $p^N$.
I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$.
My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over ${\bf Z}$?
Robert PollackFri, 04 Nov 2011 17:46:03 +0100https://ask.sagemath.org/question/8438/