Strassen's multiplication--> TypeError: 'int' object has no attribute '__getitem__'

Question

I'm writing a program for Strassen's matrix multiplication and I'm getting the following error:

    Traceback (most recent call last):
      File "StrassensMult_v01.py", line 130, in <module>
        cMatrix = matrixMul(aMatrix, bMatrix)
      File "StrassensMult_v01.py", line 92, in matrixMul
        C11 = matrixAdd(S1, matrixAdd(S4, matrixAdd(S5, S7, add), sub), add)
      File "StrassensMult_v01.py", line 73, in matrixAdd
        Sum[i].append(obj(A[i][j], B[i][j]))
    TypeError: 'int' object has no attribute '__getitem__'

Here's all the relevant code:

    #!/usr/bin/env python
    from operator import add, sub

    def Partition(A):
        '''this works. Perfect.'''
        '''Divides the given matrix into 4 different matrices'''
        order = getOrder(A)
        divVal = order/2
        a11= []
        a12= []
        a21= []
        a22= []

        for i in range(0,divVal):
            a11.append([])
            for j in range(0,divVal):
                a11[i].append(A[i][j])

        for i in range(0,divVal):
            a12.append([])
            for j in range(divVal,order):
                a12[i].append(A[i][j])

        for i in range(divVal,order):
            a21.append([])
            for j in range(0,divVal):
                a21[i-divVal].append(A[i][j])

        for i in range(divVal,order):
            a22.append([])
            for j in range(divVal,order):
                a22[i-divVal].append(A[i][j])

        return a11, a12, a21, a22

    def Combine(C11, C12, C21, C22):
        '''Freaking  finished!!!'''
        '''Combines 4 matrices into a single matrix'''
        divVal = getOrder(C11)
        order = len(C11) + len(C12)
        C = []
        for i in range(0, divVal):
            C.append([])
            for j in range(0, divVal):
                C[i].append(C11[i][j])

        for i in range(0, divVal):
            for j in range(0, divVal):
                C[i].append(C12[i][j])

        for i in range(0, divVal):
            C.append([])
            for j in range(0, divVal):
                C[divVal + i].append(C21[i][j])

        for i in range(0, divVal):
            for j in range(0,divVal):
                C[divVal + i].append(C22[i][j])

        return C



    def matrixAdd(A, B, obj):
        '''This works fine, too.'''
        '''Adds(or subtracts) two matrices based on obj function object'''
        '''Obj is for in case of matrix subtraction. Just pass a add or sub function object to it, and hey presto!'''
        order = getOrder(A)
        Sum = []
        for i in range(order):
            Sum.append([])
            for j in range(order):
                Sum[i].append(obj(A[i][j], B[i][j]))
        return Sum

    def matrixMul(A, B):
        '''Multiplies matrices based on strassen's method'''
        n = getOrder(A)
        #print n
        if n != 1:
            A11, A12, A21, A22 = Partition(A)
            B11, B12, B21, B22 = Partition(B)

            S1 = matrixMul(matrixAdd(A11, A22, add), matrixAdd(B11, B22, add))
            S2 = matrixMul(matrixAdd(A21, A22, add), B11)
            S3 = matrixMul(matrixAdd(B12, B22, sub), A11)
            S4 = matrixMul(matrixAdd(B21, B11, sub), A22)
            S5 = matrixMul(matrixAdd(A11, A12, add), B22)
            S6 = matrixMul(matrixAdd(A21, A11, sub), matrixAdd(B11, B12, add))
            S7 = matrixMul(matrixAdd(A12, A22, sub), matrixAdd(B21, B22, add))

            C11 = matrixAdd(S1, matrixAdd(S4, matrixAdd(S5, S7, add), sub), add)
            C12 = matrixAdd(S3, S5, add)
            C21 = matrixAdd(S2, S4, add)
            C22 = matrixAdd(S1, matrixAdd(S3, matrixAdd(S2, S6, add), sub), add)

            C = Combine(C11,C12, C21, C22)

        else:
            C = []
            C.append(A[0][0] * B[0][0])

        return C


    def inputVal():
        n = input('Enter the order of the square matrices you wish to multiply: ')

        print 'Enter matrix values: '
        Amat = []
        Bmat = []
        print '\n\nFor first matrix...'
        for i in range(n):
            Amat.append([])
            for j in range(n):
                Amat[i].append(input('Enter A[%s][%s]: ' %(i,j)))

        print '\n\nFor second matrix...'
        for i in range(n):
            Bmat.append([])
            for j in range(n):
                Bmat[i].append(input('Enter B[%s][%s]: ' %(i,j)))

        return Amat, Bmat
    '''Input the matrices'''
    getOrder = lambda x: len(x)
    '''Get the order of the matrix'''

    aMatrix, bMatrix = inputVal()
    cMatrix = matrixMul(aMatrix, bMatrix)
    print cMatrix

    if __name__ == '__main__':
        main()

with the equations for Strassen's being:

Assuming an nXn matrix, with n being an exact power of 2

    S1 = (A11 + A22)(B11 + B22)
    S2 = (A21 + A22) * B11
    S3 = (B12 - B22) * A11
    S4 = (B21 - B11) * A22
    S5 = (A11 + A12) * B22
    S6 = (A21 - A11) * (B11 + B12)
    S7 = (A12 - A22) * (B21 + B22)

    C11 = S1 + S4 - S5 + S7
    C12 = S3 + S5
    C21 = S2 + S4
    C22 = S1 + S3 - S2 + S6

Why is the TypeError happening? I realise that there has to be some issues with all the function linkings, but if someone points me in the right direction, that'd be great.

Answer 1

The problem is in handling of the corner case in matrixMul, for order of matrix A, n = 1.

def matrixMul(A, B):
    n = getOrder(A)
    if n != 1:
        # ...
    else:
        C = []
        C.append(A[0][0] * B[0][0])
    return C

Notice you return a list instead of matrix in that case.

To fix it, you can write it like this:

C = []
C.append([A[0][0] * B[0][0]])

or, simpler:

C = [[ A[0][0] * B[0][0] ]]