CODEWITHSUNDEEP
rlinear-algebratoeplitz
eduardokapp
eduardokapp

Reputation: 1751

Find out if input is a Toeplitz Matrix in R

Given a random matrix (any size!), write a function that determines whether or not that matrix is a Toeplitz Matrix. In linear algebra, a Toeplitz matrix is one in which the elements on any given diagonal from top left to bottom right are identical.

Here is an example:

x <- structure(c(1, 5, 4, 7, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 8, 
4, 3, 2), .Dim = 4:5)

     [,1] [,2] [,3] [,4] [,5]
[1,]    1    2    3    4    8
[2,]    5    1    2    3    4
[3,]    4    5    1    2    3
[4,]    7    4    5    1    2

So our function should receive such matrix and return TRUE if it meets the conditions.

To test the function, one can use stats::toeplitz() to generate a toeplitz matrix. So for example, the expected output of our function should be:

> toeplitz_detector(stats::toeplitz(sample(5, 5)))
> [1] TRUE

Upvotes: -2

Views: 105

Answers (1)

eduardokapp
eduardokapp

Reputation: 1751

I've solved the problem by defining the following function:

toeplitz_solver <- function(a) {
    # re-order a backwards, because we need to check diagonals from top-left
    # to bottom right. if we don't reorder, we'll end up with top-right to
    # bottom-left.
    a <- a[, ncol(a):1]

    # get all i and j (coordinates for every element)
    i <- 1:nrow(a)
    j <- 1:ncol(a)

    # get all combinations of i and j
    diags <- expand.grid(i, j)

    # the coordinates for the diagonals are the ones where
    # the sum is the same, e.g.: (3,2), (4,1), (2,3), (1,4)
    sums <- apply(diags, 1, sum)
    indexes <- lapply(unique(sums), function(x) {
        diags[which(sums  == x), ]
    })

    # indexes is now a list where every element is a list of coordinates
    # the first element is a list for every coordinates for the first diag
    # so on and so forth
    results <- sapply(indexes, function(x) {
        y <- a[as.matrix(x)]
        return(all(y == y[1]))
    })
    # if every diagonal meets the condition, it is safe to assume that the
    # input matrix is in fact toeplitz.
    return(all(results))
}

Upvotes: 0

Related Questions