## Question

Let be a given matrix with . If the time taken to compute the determinant of a square matrix of size j is , find upper bound on the total time taken to find the rank of A using determinants.

## Solution

This problem has multiple parts. So dividing the solution attempt into the respective steps that posed a challenge to me.

### Part 1: Method to find rank of a matrix using determinants

__Theory:__

Basically, we need to check if there is at least one non-zero determinant for a given order of square submatrices. An order of 2 means square submatrices of size . We need to check the same for orders etc. If for a given order k, there are no square submatrices with a non-zero determinant, then the rank of the matrix is .

__In-Context:__

Since we need to find the upper bound for the given matrix & , the orders till n has to be checked.

### Part 2: Formula of time taken to find determinant of one square submatrix of order n

Size of a square matrix of order

Size of a square matrix of order

Therefore, Size of a square matrix of order

Let time taken to find determinant of submatrix for a given size be ,

For size

(1)

### Part 3: Finding number of square submatrices of order k for a matrix of size

No. of submatrices of size for a matrix

In the case of square submatrices,

(2)

### Part 4: Total time taken to find the rank of A using determinants

Total time to find the determinants for a given order

For every order k, we will need to multiply (1) and (2) to find time taken for that order. To find time taken for all n orders, the individual products (1) * (2) of every order will have to be summed up.

I.e. for nth order,

Thus, applying summation, total time to find the rank of A using determinants

(3)

### Part 5: Finding the Upper Bound for total time taken to find the rank of A using determinants

Expanding (3),

(4)

In (4), the terms m & n are constants. Hence, let

Apply c & d in (4),

(5)

#### General summation formulae pattern:

Inference >> From general summation formulae, I infer that for every order, the highest power in the formula will increase by 1.

Using the inference & ignoring the lower powers of the resultant polynomial equation, upper bound of (5) becomes,

*Thus, the upper bound for the polynomial equation that represents the total time taken to find the rank of A using determinants is of the order 8.*

__References:__

1) Theory for finding rank using determinants.

2) Proof & formula for finding number of submatrices for a given matrix of size