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.Fri, 16 Feb 2018 14:06:40 +0100How do you calculate the branch number of a matrix?https://ask.sagemath.org/question/41152/how-do-you-calculate-the-branch-number-of-a-matrix/ Can anyone explain what a branch number is and how to calculate it? I have checked several books on matrices but it seems uncommon. In particular, the matrix:
$$02\quad 03\quad 01\quad 01$$
$$01\quad 02\quad 03\quad 01$$
$$01\quad 01\quad 02\quad 03$$
$$03\quad 01\quad 01\quad 02$$
These entries are hexadecimals (or bytes), e.g. in bits $\{02\}$ is $00000010$, and comes from the Mix column layer in the $AES$ cipher (just in case that makes a difference).
I have read this matrix has the maximum branch number of $n+1 = 5$, but I do not understand where this came from or what it means.
I also read this is an $MDS$ matrix and I think branch numbers and $MDS$ matrices are linked somehow but, again, I don't know how. I have looked for video tutorials on $MDS$ matrices and branch numbers but there is nothing for beginners.
A couple of simple examples for branch numbers and/or $MDS$ matrices would be really helpful.
Redbook1Fri, 16 Feb 2018 14:06:40 +0100https://ask.sagemath.org/question/41152/tree of vectorshttps://ask.sagemath.org/question/39425/tree-of-vectors/This is a more complicated version of
[apply functions iteratively](https://ask.sagemath.org/question/36159/apply-functions-iteratively-modified-re-post/)
I have a starting "seed" vector, say
`e1 = matrix(4,1,(1,0,0,0))`
Next, I have a collection of 4x4 matrices
`thin_group = [T1,T2,T3,T4,T5]`
where
$T1 = \left(\begin{array}{rrrr}
-1 & 0 & 0 & 0 \\\\
2 & 1 & 0 & 0 \\\\
4 & 0 & 1 & 0 \\\\
4 & 0 & 0 & 1
\end{array}\right), T2 = \left(\begin{array}{rrrr}
1 & 2 & 0 & 0 \\\\
0 & -1 & 0 & 0 \\\\
0 & 4 & 1 & 0 \\\\
0 & 4 & 0 & 1
\end{array}\right), T3 = \left(\begin{array}{rrrr}
1 & 0 & 1 & 0 \\\\
0 & 1 & 1 & 0 \\\\
0 & 0 & -1 & 0 \\\\
0 & 0 & 0 & 1
\end{array}\right), T4 = \left(\begin{array}{rrrr}
1 & 6 & 0 & 6 \\\\
0 & 3 & 0 & 2 \\\\
0 & 4 & 1 & 4 \\\\
0 & -4 & 0 & -3
\end{array}\right), T5 = \left(\begin{array}{rrrr}
3 & 0 & 0 & 2 \\\\
6 & 1 & 0 & 6 \\\\
4 & 0 & 1 & 4 \\\\
-4 & 0 & 0 & -3
\end{array}\right)$
These matrices either fix `e1` or send to a different vector. I have a "height" function, which just measures how large the vector entries are getting.
`def h(X):
return max(abs(X[0,0],abs(X[1,0]), abs(X[2,0]),abs(X[3,0]))`
I want to develop the following procedure:
`hmax = 50`
Begin applying T1,...,T5 to e1. As soon as I get a different vector (T1*e1 = (-1,2,4,4)), measure the height of that vector. If the height is below hmax (h(-1,2,4,4) = 4 < hmax = 50), store that vector somewhere. Now apply another matrix from thin_group to (-1,2,4,4), (but not T1 again). If the new vector has a height below hmax, store it, and apply another matrix from thin_group, just not the previous one. Continue this process until we reach a vector with a height larger than hmax. Once this happens, go back to the previous vector and apply a different matrix from thin_group i.e. go up a different branch of the tree. Go up this branch until hmax is exceeded, then go up a different branch, etc.. Eventually, this process will generate all thin_group images of e1 with hmax < 50. (this is probably about 50,000 vectors)
This procedure should "remember" the vectors that were counted/stored, so I'm thinking that I may be able to index each vector in the tree with a sequence (a1,a2,a3,...,an) where aj=1,2,3,4,5 to denote which matrix T1,...,T5 we applied previously.
Any/all ideas or partial solutions greatly appreciated. Thanks!Daniel LTue, 07 Nov 2017 19:01:32 +0100https://ask.sagemath.org/question/39425/Substitution using Dictionary with Matrix as Valuehttps://ask.sagemath.org/question/9075/substitution-using-dictionary-with-matrix-as-value/As a newcomer to SAGE, trying to use it to do symbolic linear algebra, I am wondering why substitution of a variable using a dictionary doesn't work in this case:
sage: aMatrix = matrix(SR,1,1)
sage: var('aVariable')
aVariable
sage: aDict = {}
sage: aDict[aVariable] = aMatrix
sage: aDict[aVariable]
[0]
but:
sage: aVariable.subs(aDict)
....
/Applications/sage/local/lib/python2.7/site-packages/sage/symbolic/expression.so in sage.symbolic.expression.Expression.substitute (sage/symbolic/expression.cpp:16025)()
/Applications/sage/local/lib/python2.7/site-packages/sage/symbolic/expression.so in sage.symbolic.expression.Expression.coerce_in (sage/symbolic/expression.cpp:11265)()
/Applications/sage/local/lib/python2.7/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._coerce_ (sage/structure/parent_old.c:3369)()
/Applications/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.coerce (sage/structure/parent.c:8912)()
TypeError: no canonical coercion from Full MatrixSpace of 1 by 1 dense matrices over Symbolic Ring to Symbolic Ring
Functionality to substitute matrices for variables seems to be indispensable to doing symbolic linear algebra, so I am sure there is a proper way to do this.
heatkernelThu, 14 Jun 2012 17:58:48 +0200https://ask.sagemath.org/question/9075/