Kronecker Product Of Two Matrices

Easy
0/40
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in companies
AdobeHPC Sphere Pvt Ltd

Problem statement

You are given a matrix ‘A’ with 'N' rows and 'M' columns and a matrix ‘B’ with 'P' rows and 'Q' columns. You have to find the Kronecker Product of both the matrices, which is defined as follows :

C = A tensor B

Let matrix A be |a11 a12 . . . a1m|
                |a21 a22 . . . a2m|
                . . . . . . . . . .
                . . . . . . . . . .
                |an1 an2 . . . anm|

Let matrix B be |b11 b12 . . . b1q|
                |b21 b22 . . . b2q|
                . . . . . . . . . .
                . . . . . . . . . .
                |bp1 bp2 . . . bpq|


Then,
C = A tensor B = |a11B a12B . . . a1mB|
                 |a21B a22B . . . a2mB|
                 . . . . . . . . . . .
                 . . . . . . . . . . .
                 |an1B an2B . . . anmB|
Example: 
Let matrix A be |a11   a12|
                |a21   a22|

Let matrix B be |b11   b12|
                |b21   b22|
                |b31   b32|

Then,
C = A tensor B = |a11B   a12B|
                 |a21B   a22B|

               = |a11b11   a11b12   a12b11  a12b12|
                 |a11b21   a11b22   a12b21  a12b22| 
                 |a11b31   a11b32   a12b31  a12b32|
                 |a21b11   a21b12   a22b11  a22b12|
                 |a21b21   a21b22   a22b21  a22b22|
                 |a21b31   a21b32   a22b31  a22b32|
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer ‘T' representing the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘M’ denoting the number of rows of the matrix and the number of columns of the first matrix ‘A’.

The next ‘N’ lines contain ‘M’ integers separated by spaces describing rows of matrix ‘A’.

The next line contains two integers ‘P’ and ‘Q’ denoting the number of rows of the matrix and the number of columns of the second matrix ‘B’.

The next ‘P’ lines contain ‘Q’ integers separated by spaces describing rows of matrix ‘B’.
Output Format: 
For each test case, on a separate line, output a single row of the Kronecker product matrix.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 30
1 <= M <= 30
1 <= P <= 30
1 <= Q <= 30
0 <= A[i][j] <= 10^3
0 <= B[i][j] <= 10^3

Time limit: 1 second
Sample Input 1:
2
2 2
1 2
3 4
2 2
0 5
6 7
3 2
1 2
3 4
1 0
2 3
0 5 2
6 7 3
Sample Output 1:
0 5 0 10
6 7 12 14
0 15 0 20
18 21 24 28
0 5 2 0 10 4
6 7 3 12 14 6
0 15 6 0 20 8    
18 21 9 24 28 12    
0 5 2 0 0 0    
6 7 3 0 0 0
Explanation For Sample Input 1:
For the first test case, the matrix obtained is just according to the multiplication rules shown above.

For the second test case, the matrix obtained is just according to the multiplication rules shown above.
Sample Input 2:
2
2 2
1 2
3 4
2 2
1 2
3 4
1 1
1
1 1
3
Sample Output 2:
1 2 2 4 
3 4 6 8 
3 6 4 8 
9 12 12 16
3
Hint

Can you observe some pattern here?

Approaches (1)
Maths

The idea is to multiply each element of the matrix ‘A’ with the matrix ‘B’ and store it in another matrix 'C'.

 

A tensor B = C = |Ci*P+k, j*Q+l = A[i][j] * B[k][l]|

 

Since we are multiplying each element of ‘A’ with the matrix ‘B’ the size of ‘ans’ array is  N*P X M*Q.

 

The algorithm is as follows:

 

  • Declare a 2D array, ‘ans’ with N*P number of rows and M*Q number of columns.
  • Iterate from i = 0 to N,
    • Iterate from j = 0 to M,
      • Iterate from k = 0 to P,
        • Iterate from l = 0 to Q,
          • Set ans[i * P + k][j * Q + l] to A[i][j] * B[k][l].
  • Return ‘ans’.
Time Complexity

O(N * M * P * Q), Where 'N' and 'M' denote the number of rows of the matrix and the number of columns of the matrix ‘A’, and ‘P’ and ‘Q’ denote the number of rows of the matrix and the number of columns of the matrix ‘B’.

 

Since we are multiplying each element of matrix ‘A’ with matrix ‘B’, so, each element gets multiplied by P*Q elements. 

 

Hence, the overall time complexity is O(N * M * P * Q).

Space Complexity

O(1)

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Kronecker Product Of Two Matrices
Full screen
Console