Using matrix algebra to control rows: is this possible?

Question

I am trying to use matrix algebra to manipulate strings. This means the possibility of multiple matrix structures using concatenation and insertion of a string or array of strings.

Earlier, I tried to implement a thing on R, but this was impossible, since matrices can only have one-dimensional records.

I hope there is enough language - agnostic and abstract, but for clarity, I will use the R-code. I have to make it clear that I do not require real matrices, but a matrix-like structure on which we can do multiplication by matrices and extract an element (ij) of the structure.

{+, *} MATRIX MATERIALS

{+, *} - the product of two square matrices A and B of dimension n is a matrix C defined by the elements: C _{i, j} = Sum _{k = 1, ..., n} A _{i, k} * B _{k, j} .

For example, consider the matrix M <- matrix(c(a,b,0,0,c,d,0,0,e),3,3) . Then M times M is M <- matrix(c(a^2,a*b+b*c,b*d,0,c^2,c*d+d*e,0,0,e^2),3,3) .

{c (,), paste0 (,)} MATRIX MATERIALS

The rule of this operation, which I would like to implement, coincides with the previous stated multiplication with a significant mutation, that the sum should be concatenation, and the product should be paste. In other words, if in the previous formula we found a+b , now the result should be "c (a, b)", and when we find a*b , we should now read it as paste0(a,b) .

It is necessary to observe some of the usual properties, namely distribution properties and properties of element 0. Therefore, if a <- c("q",0,"w") and b <- c("e") , then a*b <- c("qe",0,"we") (and we should freely forget element 0 by discarding it, as this will not affect the calculation.

In addition, we multiply uniform matrices, so each element C _{i, j} = Sum _{k = 1, ..., n} A _{i, k} * B _{k, j} should now be read as c("A[i,1]B[1,j]",...,"A[i,n]B[n,j]") .

Finally, a matrix similar to the results should be what we can use again for calculations (for example, to make more complex calculations like mult (mult (A, B), C), etc.).

SIMPLE CASE

For simplicity, we begin by computing products of the form mult(A,A) , mult(mult(A,A),A) , etc. We can also impose A on a simple matrix, which means that each of its elements is a one-dimensional row, and not a concatenation of the row.

We give an example. Let A be a three-dimensional matrix defined as A <- matrix(c("a","b",0,0,"c","d",0,0,"e"),3,3) , then multiplication A times A must be mult(A,A) = matrix(c("aa",c("ab","bc"),"bd",0,"cc",c("cd","de"),0,0,"ee"),3,3) and A ³ should be mult(mult(A,A),A) = matrix(c("aaa",c("aab","abc","bcc"),c("abd","bcd","bde"),0,"ccc",c("ccd","cde","dee"),0,0,"eee"),3,3) .

Question

How would you implement this? Which language seems more appropriate?

Answer 1

Here are some ideas for symbolic animation of matrices in R:

First we need to define the scalar product of the row and column. This can be done with:

 wrap <- function(x) paste0("(",x,")") rowcol <- function(row,col) paste(wrap(row),wrap(col),sep="*",collapse="+") 

Example:

 > rowcol(c("A","B","C"),c("D","E","F")) [1] "(A)*(D)+(B)*(E)+(C)*(F)" 

I had to “wrap” each element in parentheses, since privileges greater than 2 can have more replicated expressions than one variable or a number (zero). Also note that zero will be displayed normally, i.e. He does not know (yet) that they can be simplified:

 > rowcol(c("A","B"),c("0","X+Y")) [1] "(A)*(0)+(B)*(X+Y)" 

Since these are valid expressions in R, this fact can be used to write a simplification function to eliminate zeros and redundant brackets. I will get there.

Now matrix multiplication and degrees are simple:

 symprod <- function(A,B) sapply(1:ncol(B), function(j)sapply(1:nrow(A), function(i)rowcol(A[i,],B[,j]))) sympow <- function(A,n) { B <- A; for( i in seq_len(n-1) ) B <- symprod(B,A); B } 

They create reliable (albeit awkward) expressions:

 > A <- matrix(LETTERS[1:4],2,2) > diag(A) <- 0 > sympow(A,3) [,1] [,2] [1,] "((0)*(0)+(C)*(B))*(0)+((0)*(C)+(C)*(0))*(B)" "((0)*(0)+(C)*(B))*(C)+((0)*(C)+(C)*(0))*(0)" [2,] "((B)*(0)+(0)*(B))*(0)+((B)*(C)+(0)*(0))*(B)" "((B)*(0)+(0)*(B))*(C)+((B)*(C)+(0)*(0))*(0)" 

Now let's talk about simplification. These strings can be parsed into real R expressions, because they conform to the R standard. Variables need not be defined because we will not evaluate expressions. In fact, I just want to analyze them in order to simplify the simplification.

Check out the feature below. It removes the extra parentheses, replaces the null value with zero, and removes the premises (in addition) that are zero:

 simplify <- function(e) { if( mode(e) %in% c("name","numeric") ) return(e) if( as.character(e[[1]])=="+" ) { x <- simplify(e[[2]]) y <- simplify(e[[3]]) if( identical(x,0) ) return(y) if( identical(y,0) ) return(x) return(call("+", x, y)) } if( as.character(e[[1]])=="*" ) { x <- simplify(e[[2]]) if( identical(x,0) ) return(0) y <- simplify(e[[3]]) if( identical(y,0) ) return(0) return(call("*", x, y)) } if( as.character(e[[1]])=="(" ) { x <- simplify(e[[2]]) if( mode(x) %in% c("name","numeric") ) return(x) return(call("(", x)) } } 

This function works with the call object. To use with strings we need

 simplify_text <- function(s) deparse(simplify(parse(text=s)[[1]])) 

Example:

 > simplify_text("(x)+(0*(a+b))+(z)") [1] "x + z" 

If you want, you can use it as a wrapper for rowcol :

 rowcol <- function(row,col) simplify_text(paste(wrap(row),wrap(col),sep="*",collapse="+")) 

Result:

 > sympow(A,3) [,1] [,2] [1,] "0" "(C * B) * C" [2,] "(B * C) * B" "0" 

Some other simplifications may be written, it depends on how you plan to work with them. But, if the input matrices are strings of valid expressions, the final result remains valid.

---

EDIT: another approach for rowcol :

Consider the following functions:

 cellprod <- function(r, s) { z <- expand.grid(r,s, stringsAsFactors=FALSE) filter <- (z$Var1 != 0) & (z$Var2 != 0) paste(z$Var1[filter], z$Var2[filter], sep="*", collapse="+") } rowcol <- function(row,col) { x <- strsplit(row, "\\+") y <- strsplit(col, "\\+") L <- vapply(seq_along(x), function(i) cellprod(x[[i]],y[[i]]), character(1)) filter <- nzchar(L) if( ! any(filter) ) return("0") paste(L[filter], collapse="+") } 

Using these functions instead of the functions indicated above, we can process matrices with expressions of the form x*y*z+a*b+f , i. e. the sum of the products in each cell. The functions automatically apply the distribution law, preserving the form (the sum of products), and also automatically removes zeros. Last example above:

 > sympow(A,3) [,1] [,2] [1,] "0" "C*B*C" [2,] "B*C*B" "0" 

No simplification required! Another example:

 > A <- matrix(LETTERS[1:9],3,3) > B <- matrix(LETTERS[10:18],3,3) > A[2,3] <- 0 > A[3,2] <- 0 > B[1,3] <- 0 > B[3,1] <- 0 > A [,1] [,2] [,3] [1,] "A" "D" "G" [2,] "B" "E" "0" [3,] "C" "0" "I" > B [,1] [,2] [,3] [1,] "J" "M" "0" [2,] "K" "N" "Q" [3,] "0" "O" "R" > symprod(A,B) [,1] [,2] [,3] [1,] "A*J+D*K" "A*M+D*N+G*O" "D*Q+G*R" [2,] "B*J+E*K" "B*M+E*N" "E*Q" [3,] "C*J" "C*M+I*O" "I*R"