uniform matroids and MDS codes

Posted on 2010/03/10 by wdjoyner

It is known that uniform (resp. paving) matroids correspond to MDS (resp. “almost MDS” codes). This post explains this connection.

An MDS code is an $[n,k,d]$ linear error correcting block code $C$ which meets the Singleton bound, $d+k=n+1$ . A uniform matroid is a matroid for which all circuits are of size $\geq r(M)+1$ , where $r(M)$ is the rank of M. Recall, a circuit in a matroid M=(E,J) is a minimal dependent subset of E — that is, a dependent set whose proper subsets are all independent (i.e., all in J).

Consider a linear code $C$ whose check matrix is an $(n-k)\times n$ matrix $H=(\vec{h}_1,\dots , \vec{h}_n)$ . The vector matroid M=M[H] is a matroid for which the smallest sized dependency relation among the columns of H is determined by the check relations $c_1\vec{h}_1 + \dots + c_n \vec{h}_n = H\vec{c}=\vec{0}$ , where $\vec{c}=(c_1,\dots,c_n)$ is a codeword (in C which has minimum dimension d). Such a minimum dependency relation of H corresponds to a circuit of M=M[H].

Floyd-Warshall-Roy, 3

Posted on 2010/03/02 by wdjoyner

As in the previous post, let $G=(V,E)$ be a weighted digraph having $n$ vertices and let $A=A_G$ denote its $n\times n$ adjacency matrix. We identify the vertices with the set $\{1,2,\dots, n\}$ .

The previous post discussed the following result, due to Sturmfels et al.

Theorem: The entry of the matrix A^n-1 in row i and column j equals the length of a shortest path from vertex i to vertex j in G. (Here A^n-1 denotes the n-1-st tropical power of A.)

This post discusses an implementation in Python/Sage.

Consider the following class definition.

class TropicalNumbers:
    """
    Implements the tropical semiring.

    EXAMPLES:
        sage: T = TropicalNumbers()
        sage: print T
        Tropical Semiring

    """
    def __init__(self):
        self.identity = Infinity

    def __repr__(self):
        """
        Called to compute the "official" string representation of an object.
        If at all possible, this should look like a valid Python expression
        that could be used to recreate an object with the same value.

        EXAMPLES:
            sage: TropicalNumbers()
            TropicalNumbers()

        """
        return "TropicalNumbers()"

    def __str__(self):
        """
        Called to compute the "informal" string description of an object. 

        EXAMPLES:
            sage: T = TropicalNumbers()
            sage: print T
            Tropical Semiring

        """
        return "Tropical Semiring"

    def __call__(self, a):
        """
        Coerces a into the tropical semiring.

        EXAMPLES:
            sage: T(10)
            TropicalNumber(10)
            sage: print T(10)
            Tropical element 10 in Tropical Semiring
        """
        return TropicalNumber(a)

    def __contains__(self, a):
        """
        Implements "in".

        EXAMPLES:
            sage: T = TropicalNumbers()
            sage: a = T(10)
            sage: a in T
            True

        """
        if a in RR or a == Infinity:
            return a==Infinity or (RR(a) in RR)
        else:
            return a==Infinity or (RR(a.element) in RR)

class TropicalNumber:
    def __init__(self, a):
        self.element = a
        self.base_ring = TropicalNumbers()

    def __repr__(self):
        """
        Called to compute the "official" string representation of an object.
        If at all possible, this should look like a valid Python expression
        that could be used to recreate an object with the same value.

        EXAMPLES:

        """
        return "TropicalNumber(%s)"%self.element

    def __str__(self):
        """
        Called to compute the "informal" string description of an object. 

        EXAMPLES:
            sage: T = TropicalNumbers()
            sage: print T(10)
            Tropical element 10 in Tropical Semiring
        """
        return "%s"%(self.number())

    def number(self):
        return self.element

    def __add__(self, other):
        """
        Implements +. Assumes both self and other are instances of
        TropicalNumber class.

        EXAMPLES:
            sage: T = TropicalNumbers()
            sage: a = T(10)
            sage: a in T
            True
            sage: b = T(15)
            sage: a+b
            10

        """
        T = TropicalNumbers()
        return T(min(self.element,other.element))

    def __mul__(self, other):
        """
        Implements multiplication *.

        EXAMPLES:
            sage: T = TropicalNumbers()
            sage: a = T(10)
            sage: a in T
            True
            sage: b = T(15)
            sage: a*b
            25
        """
        T = TropicalNumbers()
        return T(self.element+other.element)

class TropicalMatrix:
    def __init__(self, A):
        T = TropicalNumbers()
        self.base_ring = T
        self.row_dimen = len(A)
        self.column_dimen = len(A[0])
        # now we coerce the entries into T
        A0 = A
        m = self.row_dimen
        n = self.column_dimen
        for i in range(m):
            for j in range(n):
                A0[i][j] = T(A[i][j])
        self.array = A0

    def matrix(self):
        """
        Returns the entries (as ordinary numbers).

        EXAMPLES:
            sage: A = [[0,1,3,7],[2,0,1,3],[4,5,0,1],[6,3,1,0]]
            sage: AT = TropicalMatrix(A)
            sage: AT.matrix()
            [[0, 1, 3, 7], [2, 0, 1, 3], [4, 5, 0, 1], [6, 3, 1, 0]]
        """
        m = self.row_dim()
        n = self.column_dim()
        A0 = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                A0[i][j] = (self.array[i][j]).number()
        return A0

    def row_dim(self):
        return self.row_dimen

    def column_dim(self):
        return self.column_dimen

    def __repr__(self):
        """
        Called to compute the "official" string representation of an object.
        If at all possible, this should look like a valid Python expression
        that could be used to recreate an object with the same value.

        EXAMPLES:

        """
        return "TropicalMatrix(%s)"%self.array

    def __str__(self):
        """
        Called to compute the "informal" string description of an object. 

        EXAMPLES:

        """
        return "Tropical matrix %s"%(self.matrix())

    def __add__(self, other):
        """
        Implements +. Assumes both self and other are instances of
        TropicalMatrix class.

        EXAMPLES:
            sage: A = [[1,2,Infinity],[3,Infinity,0]]
            sage: B = [[2,Infinity,1],[3,-1,1]]
            sage: AT = TropicalMatrix(A)
            sage: BT = TropicalMatrix(B)
            sage: AT
            TropicalMatrix([[TropicalNumber(1), TropicalNumber(2), TropicalNumber(+Infinity)],
              [TropicalNumber(3), TropicalNumber(+Infinity), TropicalNumber(0)]])
            sage: AT+BT
            [[TropicalNumber(1), TropicalNumber(2), TropicalNumber(1)],
             [TropicalNumber(3), TropicalNumber(-1), TropicalNumber(0)]]
        """
        A = self.array
        B = other.array
        C = []
        m = self.row_dim()
        n = self.column_dim()
        if m != other.row_dim:
            raise ValueError, "Row dimensions must be equal."
        if n != other.column_dim:
            raise ValueError, "Column dimensions must be equal."
        for i in range(m):
            row = [A[i][j]+B[i][j] for j in range(n)] # + as tropical numbers
            C.append(row)
        return C

    def __mul__(self, other):
        """
        Implements multiplication *.

        EXAMPLES:
            sage: A = [[1,2,Infinity],[3,Infinity,0]]
            sage: AT = TropicalMatrix(A)
            sage: B = [[2,Infinity],[-1,1],[Infinity,0]]
            sage: BT = TropicalMatrix(B)
            sage: AT*BT
             [[TropicalNumber(1), TropicalNumber(3)],
              [TropicalNumber(5), TropicalNumber(0)]]
            sage: A = [[0,1,3,7],[2,0,1,3],[4,5,0,1],[6,3,1,0]]
            sage: AT = TropicalMatrix(A)
            sage: A = [[0,1,3,7],[2,0,1,3],[4,5,0,1],[6,3,1,0]]
            sage: AT = TropicalMatrix(A)
            sage: print AT*AT*AT
            Tropical matrix [[0, 1, 2, 3], [2, 0, 1, 2], [4, 4, 0, 1], [5, 3, 1, 0]]
        """
        T = TropicalNumbers()
        A = self.matrix()
        B = other.matrix()
        C = []
        mA = self.row_dim()
        nA = self.column_dim()
        mB = other.row_dim()
        nB = other.column_dim()
        if nA != mB:
            raise ValueError, "Column dimension of A and row dimension of B must be equal."
        for i in range(mA):
            row = []
            for j in range(nB):
                c = T(Infinity)
                for k in range(nA):
                    c = c+T(A[i][k])*T(B[k][j])
                row.append(c.number())
            C.append(row)
        return TropicalMatrix(C)

This shows that the shortest distances of digraph with adjacency matrix $\begin{pmatrix} 0&1&3&7\\ 2&0&1&3\\ 4&5&0&1\\ 6&3&1&0\end{pmatrix},$ is equal to A³, which is equal to $\begin{pmatrix} 0&1&2&3\\ 2&0&1&2\\ 4&4&0&1\\ 5&3&1&0\end{pmatrix}.$ This verifies an example given in chapter 1 of the book by Maclagan and Sturmfels, Introduction to Tropical Geometry .

Floyd-Warshall-Roy, 2

Posted on 2010/02/20 by wdjoyner

Let $G = (V,E)$ be a weighted digraph having $n$ vertices and let $A = A_G$ denote its $n \times n$ adjacency matrix. We identify the vertices with the set $\{1,2,\dots, n\}$ . As mentioned in the previous post, the FWR algorithm is an example of dynamic programming. In the book Algebraic Statistics for Computational Biology by L. Pachter and B. Sturmfels, and the book Introduction to Tropical Geometry by D Maclagan and Sturmfels, this algorithm is described using the tropical matrix powers of $A$ . In fact, in the latter book, the corresponding section is titled “Dynamic programming”. They formulate it “tropically” as follows.

Theorem: The entry of the matrix A^n-1 in row i and column j equals the length of a shortest path from vertex i to vertex j in G. (Here A^n-1 denotes the n-1-st tropical power of A.)

How do you compute the tropical power of a matrix? Tropical matrix arithmetic (addition and multiplication) is the obvious extension of the addition and multiplication operations on the tropical semiring. This semiring, $({\mathbb{R}} \cup \{\infty \}, \oplus, \odot)$ , is defined with the operations as follows: $x \oplus y = {\rm min}(x,y)$ , $x \odot y = x+y$ . The ordinary product of two $n\times n$ matrices takes $O(n^3)$ operations (roughly the same number of additions and multiplications). The tropical product of two $n\times n$ matrices still takes $O(n^3)$ operations (but only additions and comparisons, no multiplications). Of course, ordinary powers, as well as tropical powers, can be computed using the repeated squaring algorithm. This implies that the complexity of computing the N-th (tropical) power of an $n \times n$ matrix A is $O(M\log(N))$ , where M is the complexity of computing the (tropical) product of two $n \times n$ matrices.

At the current time, the complexity of ordinary matrix multiplication is best estimated by either Strassen’s algorithm (for practical use) or the Coppersmith-Winograd algorithm (for theoretically best known). The CW algorithm can multiply two $n \times n$ matrices in $O(n^{2.376})$ time. However, the implied “big-O” constant is so large that the algorithm is not practical. Strassen’s algorithm can multiply two $n \times n$ matrices in $O(n^{\log_2(7)+o(1)})=O(n^{2.807})$ time.

Question: Do these complexity estimates extend to tropical matrix multiplication?

If so, then the complexity of computing the matrix A^n-1 is $O(n^{2.807})$ , using Strassen’s algorithm. This is better than the $O(n^3)$ estimate for the FWR algorithm mentioned in the previous post.

In fact, these observations seem so “obvious” that the fact that Sturmfels did not mention them in two different books, makes me wonder if the above question is more difficult to answer than it seems!

Floyd-Warshall-Roy

Posted on 2010/02/08 by wdjoyner

The Floyd-Warshall-Roy algorithm is an algorithm for finding shortest paths in a weighted, directed graph. It allows for negative edge weights and detects a negative weight cycle if one exists. Assuming that there are no negative weight cycles, a single execution of the FWR algorithm will find the shortest paths between all pairs of vertices.

This algorithm is an example of dynamic programming, which allows one to break the computation down to simpler steps using some sort of recursive procedure. If $n=|V|$ then this is a $O(n^3)$ -time algorithm. For comparison, the Bellman-Ford algorithm has complexity $O(|V|\cdot |E|)$ , which is $O(n^3)$ -time for “dense” graphs. However, Bellman-Ford only yields the shortest paths eminating from a single vertex. To achieve comparable output, we would need to iterate Bellman-Ford over all vertices, which would be an $O(n^4)$ -time algorithm for “dense” graphs. Except for “sparse” graphs, Floyd-Warshall-Roy is better than an interated implementation of Bellman-Ford.

Here is a Sage implementation

def floyd_warshall_roy(A):
    """
    Shortest paths

    INPUT: 
        A - weighted adjacency matrix 

    OUTPUT
        dist  - a matrix of distances of shortest paths
        paths - a matrix of shortest paths

    EXAMPLES:
        sage: A = matrix([[0,1,2,3],[0,0,2,1],[20,10,0,3],[11,12,13,0]]); A
        sage: floyd_warshall_roy(A)
        ([[0, 1, 2, 2], [12, 0, 2, 1], [14, 10, 0, 3], [11, 12, 13, 0]], 
          [-1  1  2  1]
          [ 3 -1  2  3]
          [ 3 -1 -1  3]
          [-1 -1 -1 -1])
        sage: A = matrix([[0,1,2,4],[0,0,2,1],[0,0,0,5],[0,0,0,0]])
        sage: floyd_warshall_roy(A)
        ([[0, 1, 2, 2], [+Infinity, 0, 2, 1], [+Infinity, +Infinity, 0, 5],
          [+Infinity, +Infinity, +Infinity, 0]], 
          [-1  1  2  1]
          [-1 -1  2  3]
          [-1 -1 -1  3]
          [-1 -1 -1 -1])
        sage: A = matrix([[0,1,2,3],[0,0,2,1],[-5,0,0,3],[1,0,1,0]]); A
        sage: floyd_warshall_roy(A)
        Traceback (click to the left of this block for traceback)
        ...
        ValueError: A negative edge weight cycle exists.
        sage: A = matrix([[0,1,2,3],[0,0,2,1],[-1/2,0,0,3],[1,0,1,0]]); A
        sage: floyd_warshall_roy(A)
        ([[0, 1, 2, 2], [3/2, 0, 2, 1], [-1/2, 1/2, 0, 3/2], [1/2, 3/2, 1, 0]],
          [-1  1  2  1]
          [ 2 -1  2  3]
          [-1  0 -1  1]
          [ 2  2 -1 -1])
    """
    G = Graph(A, format="weighted_adjacency_matrix")
    V = G.vertices()
    E = [(e[0],e[1]) for e in G.edges()]
    n = len(V)
    dist = [[0]*n for i in range(n)]
    paths = [[-1]*n for i in range(n)]
    # initialization step
    for i in range(n):
        for j in range(n):
            if (i,j) in E:
                paths[i][j] = j
            if i == j:
                dist[i][j] = 0
            elif A[i][j] != 0:
                dist[i][j] = A[i][j]
            else:
                dist[i][j] = infinity
    # iteratively finding the shortest path
    for j in range(n):
        for i in range(n):
            if i != j:
                for k in range(n):
                    if k != j:
                        if dist[i][k]>dist[i][j]+dist[j][k]:
                            paths[i][k] = V[j]
                        dist[i][k] = min(dist[i][k], dist[i][j] +dist[j][k])
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError, "A negative edge weight cycle exists."
    return dist, matrix(paths)

Sage and the future of mathematics

Posted on 2010/02/04 by wdjoyner

I am not a biologist nor a chemist, and maybe neither are you, but suppose we were. Now, if I described a procedure, in “standard” detail, to produce a result XYZ, you would (based on your reasonably expected expertise in the field), follow the steps you believe were described and either reproduce XYZ or, if I was mistaken, not be able to reproduce XYZ. This is called scientific reproducibility. It is cructial to what I believe is one of the fundamental principles of science, namely Popper’s Falsifiability Criterion.

More and more people are arguing, correctly in my opinion, that in the computational realm, in particular in mathematical research which uses computational experiments, that much higher standards are needed. The Ars Technica article linked above suggests that “it’s time for a major revision of the scientific method.” Also, Victoria Stodden argues one must “facilitate reproducibility. Without this data may be open, but will remain de facto in the ivory tower.” The argument basically is that to reproduce computational mathematical experiments is unreasonably difficult, requiring more that a reasonable expertise. These days, it may in fact (unfortunately) require purchasing very expensive software, or possessing of very sophisticated programming skills, accessibility to special hardware, or (worse) guessing parameters and programming procedures only hinted at by the researcher.

Hopefully, Sage can play the role of a standard bearer for such computational reproducibility. Sage is free, open source and there is a publically available server it runs on (sagenb.org).

What government agencies should require such reproducibility? In my opinion, all scientific funding agencies (NSF, etc) should follow these higher standards of computational accountability.

Bases of representable/vector matroids in Sage

Posted on 2010/02/01 by wdjoyner

A matroid M is specified by a set X of “points” and a collection B of “bases, where $X \subset 2^X$ , satisfying certain conditions (see, for example, Oxley’s book, Matroid theory).

One way to construct a matroid, as it turns out, is to consider a matrix M with coefficients in a field F. The column vectors of M are indexed by the numbers $J = \{1,2,\dots,n\}$ . The collection B of subsets of J associated to the linearly independent column vectors of M of cardinality $r = rank_F(M)$ forms a set of bases of a matroid having points $X=J$ .

How do you compute B? The following Sage code should work.



def independent_sets(mat):
    """
    Finds all independent sets in a vector matroid.

    EXAMPLES:
        sage: M = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: M
        [1 0 0 1 1 0]
        [0 1 0 1 0 1]
        [0 0 1 0 1 1]
        sage: independent_sets(M)  
        [[0, 1, 2], [], [0], [1], [0, 1], [2], [0, 2], [1, 2], 
        [0, 1, 4], [4], [0, 4], [1, 4], [0, 1, 5], [5], [0, 5], 
        [1, 5], [0, 2, 3], [3], [0, 3], [2, 3], [0, 2, 5], [2, 5], 
        [0, 3, 4], [3, 4], [0, 3, 5], [3, 5], [0, 4, 5], [4, 5], 
        [1, 2, 3], [1, 3], [1, 2, 4], [2, 4], [1, 3, 4], [1, 3, 5], 
        [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5]]
        sage: M = matrix(GF(3), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: independent_sets(M)
        [[0, 1, 2], [], [0], [1], [0, 1], [2], [0, 2], [1, 2], 
        [0, 1, 4], [4], [0, 4], [1, 4], [0, 1, 5], [5], [0, 5], 
        [1, 5], [0, 2, 3], [3], [0, 3], [2, 3], [0, 2, 5], [2, 5], 
        [0, 3, 4], [3, 4], [0, 3, 5], [3, 5], [0, 4, 5], [4, 5], 
        [1, 2, 3], [1, 3], [1, 2, 4], [2, 4], [1, 3, 4], [1, 3, 5], 
        [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
        sage: M345 = matrix(GF(2), [[1,1,0],[1,0,1],[0,1,1]])
        sage: M345.rank()
        2
        sage: M345 = matrix(GF(3), [[1,1,0],[1,0,1],[0,1,1]])
        sage: M345.rank()
        3
    """
    F = mat.base_ring()
    n = len(mat.columns())
    k = len(mat.rows())
    J = Combinations(n,k)
    indE = []
    for x in J:
        M = matrix([mat.column(x[0]),mat.column(x[1]),mat.column(x[2])])
        if k == M.rank():     # all indep sets of max size
            indE.append(x)
            for y in powerset(x): # all smaller indep sets
                if not(y in indE):
                    indE.append(y)
    return indE

def bases(mat, invariant = False):
    """
    Find all bases in a vector/representable matroid.

    EXAMPLES:
        sage: M = matrix(GF(2), [[1,0,0,1,1,0],[0,1,0,1,0,1],[0,0,1,0,1,1]])
        sage: bases(M)

        [[0, 1, 2],
         [0, 1, 4],
         [0, 1, 5],
         [0, 2, 3],
         [0, 2, 5],
         [0, 3, 4],
         [0, 3, 5],
         [0, 4, 5],
         [1, 2, 3],
         [1, 2, 4],
         [1, 3, 4],
         [1, 3, 5],
         [1, 4, 5],
         [2, 3, 4],
         [2, 3, 5],
         [2, 4, 5]]
        sage: L = [x[1] for x in bases(M, invariant=True)]; L.sort(); L
         [5, 16, 17, 33, 37, 44, 45, 48, 81, 84, 92, 93, 96, 112, 113, 116]
    """
    r = mat.rank()
    ind = independent_sets(mat)
    B = []
    for x in ind:
        if len(x) == r:
            B.append(x)
    B.sort()
    if invariant == True:
        B = [(b,sum([k*2^(k-1) for k in b])) for b in B]
    return B

Evil spkgs?

Posted on 2009/08/01 by wdjoyner

In Matlab, a plugin is called a “toolkit”. In Photoshop, a plugin is called a plugin:-) As the success of Photoshop and Matlab suggest, plugins are very important. They enable “third party” developers to write specialized applications for your software package.

In Sage, (www.sagemath.org) a plugin is called an “spkg” (short for Sage PacKaGe).

Here is an easy-to-follow recipe for making an evil spkg.

Make sure that your spkg modifies and existing Python or Cython file in the Sage devel tree. Extra evil bonus points for modifying heavily used files, such as in the plot subdirectory, and the more files touched the more evil points you earn. AFAIK, this will insure that, once your “innocent” spkg is applied to a developers tree, he cannot write a trac patch which can be correctly applied to a fresh clone.
Make sure you ruin another spkg (surreptitiously, for extra bonus points). The more important the spkg you hose, the more evil points you get.

I wonder how Matlab and Photoshop avoid evil plugins?

Google and the future of academic journals?

Posted on 2009/07/17 by wdjoyner

Let us assume that google’s basic philosophy is to make information free (see for example http://www.google.com/corporate/tenthings.html) This way they can increase the value of the internet and the value of their search technology.

What can Google do to help the problem of the inflation of academic journals? The fundamental issue is the disparity between the ease of communicating information (scientific information which is, by community consensus, free) and the relatively difficult implementation of the nature human desire to make money by selling access to that information. The basic economic model is that taxpayers are the primary support for academic research at a US class I or a European university (tuition actually only fund a minority share of the cost of running an academic institution). On the other hand, taxpayers also pay for the cost of these journals to these academic institutions. If you, a typical taxpayer, enjoy paying twice or getting double-billed, I have two bridges in Brooklyn I’d like sell you.

In case the typical taxpayer thinks this is an issue they can hide from, I warn you, some of these journals are not cheap (eg, some are on the order of a few thousand dollars per issue). Moreover, some publishers, such as Reed Elsevier not only charge a couple of grand per issue but also publishes bogus journals (see for example (http://laikaspoetnik.wordpress.com/2009/05/08/mercks-ghostwriters-haunted-papers-and-fake-elsevier-journals/) and pays for fake positive reviews (http://golem.ph.utexas.edu/category/2009/07/elsevier_pays_for_favorable_bo.html).

The solution to this dilemma is rather simple, Taxpayers must insist that their research dollars only fund research which is available for free. In other words, the results of the their funded research much be publicly available. This goes for papers and software supported by their funding.

As a matter of complete disclosure, some institutions now require that their faculty post their research papers on free web servers (for example MIT), and some funding agencies require taht thier grantees make available their grantees research papers available on such servers (for example, NIH in the US).

Can Google play a role here? I think so.

Hadamard’s maximal determinant problem

Posted on 2009/06/27 by wdjoyner

This blog entry is to remind or introduce to people the fascinating problem called the Hadamard maximal determinant problem: What is the maximal possible determinant of a matrix M whose entries are of absolute value at most 1? Hadamard proved that if M is a complex matrix of order n, whose entries are bounded by $|M_{ij}| \leq 1$ , for each i, j between 1 and n, then
$|det(M)| \leq n^{n/2}$ (equality is attained, so this is best possible for such matrices).

If instead the entries of the matrix are +1 or -1 and the size of the matrix is nxn where n is a multiple of 4, then the problem of the maximal determinant presumably boils down to the well-known search for Hadamard matrices. This is discussed in many books, papers and website but in particular, I refer to

http://en.wikipedia.org/wiki/Hadamard_matrix
http://www.research.att.com/~njas/hadamard/
Hadamard matrices and their applications, by K. J. Horadam
http://www.uow.edu.au/~jennie/hadamard.html

What I think is fascinating is the entries of the matrix are only assumed to be real and not of size 4kx4k. In this case, the maximal value of the determinant is less clear. The results are complicated and depend in a fascinating way on the congruence class of n mod 4. Please see the excellent webpages (maintained by Will Orrick and Bruce Solomon)

http://www.indiana.edu/~maxdet/, and in particular,
http://www.indiana.edu/~maxdet/bounds.html

In particular, the case of an nxn matrix with n=4k+3 seems to be open.

Sage at the NSF-CDI+ECCAD conferences

Posted on 2009/05/07 by wdjoyner

This is a very quick view of some highlights of the conference http://www4.ncsu.edu/~kaltofen/NSF_WS_ECCAD09_Itinerary.html. I think further details of the talks will appear on the conference webpage later. This is very incomplete – just a few thought I was able to
jot down correctly.

Panel discussion:
Q1: What are the grand challenges of symbolic computing?
Is the term “symbolic computation” to broad? (Hybrid symbolic/numerical, algebraic geometric computation, algebraic combinatorial/group-theoretical, computer proofs, tensor calculations, differential, mathematical knowledge/database research, user interfaces, …)

General ans: No. Hoon Hong points out that user interfaces are lower level but below to the same group.

Q2: How can the latest algorithmic advances be made readily available: google analog of problem formulation? (Idea: suppose someone has a clever idea for a good algorithm but not enough discipline to implement it …)

One answer: Sage can put software together – is this the right way? Analog of stackoverflow.com?

Q3: What is the next killer app for symbolic computation? (Oil app of Groebner bases, cel phone app, robotics, …)

Q4: Can academically produced software such as LAPACK, LINBOX, SAGE compete with commercial software?

Hoon Hong answer: Yes but why? Why not cooperate. Support Sage very much but more research on interfaces and integration of different systems could lead to cooperation of the commercial systems with Sage.

Another panel:
Q: What are the spectacular successes and failures of computer algebra?

Failures:
(a) Small number of researchers.
(b) Sage could fail from lack of lies with the symbolic/numerical community (as Maxima/Axiom did). Matlab may fail due to uphill battle to integrate Mupad into good symbolic toolbox. (Many voiced view that Matlab is strong because of its many toolboxes, on the panel and privately.)
(c) Education at the High School level using CA.
(d) Presenting output of CA intelligently and in a standard format.
(e) Failure to teach people how to properly use a CA system.

Successes:
(a) Sage – interesting new effort (with caveat above)
(b) Groebner bases, LLL.

My talk on Sage raised a lot of questions. My There is both strong support for Sage and some questions on its design philisophy. My page 6 at http://sage.math.washington.edu/home/wdj/expository/nsf-eccad2009/
was a source of lots of questions.

At ECCAD http://www.cs.uri.edu/eccad2009/Welcome.html, Sage was mentioned a few times in talks as well as in some posters. The “main” Sage event was a laptop software demo Which Karl-Dieter Crisman set up for Sage.

Overall, a good experience for Sage.