[Solved]: What is the complexity of multiplying a matrix by a scalar?

Problem Detail: 

I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$?

In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like to calculate the transpose of this graph, i.e., inverse the directions of the edges. I think that if I multiply $M$ by $-1$ I will get the transposed graph. Am I right?

• If I am right, what is the complexity of multiplying a matrix by a scalar?
• If I am not, where is my mistake and what is the complexity of multiplying a matrix by a scalar anyway?

I think the complexity is $\Theta(n\cdot m)$.

Thanks.

Asked By : Azzo

Answered By : Rick Decker

In general, if you have an $n\times m$ matrix $A=(a_{i,j})$ with $1\le i\le n$ and $1\le j\le m$ then there will be $nm$ entries in the array. To multiply $A$ by a scalar $c$ you multiply each element by c, which (assuming multiplication can be done in constant time) will take $nm$ multiplications. That's not the way to go, though, if $A$ is the adjacency matrix of a directed graph.

For your peoblem, if $A$ is the adjacency matrix of a digraph $G$ on $n$ vertices, then $A$ will be an $n\times n$ matrix $(a_{i, j})$ with $a_{i,j}=1$ when there is a directed edge $e=(i, j)$ from vertex $i$ to vertex $j$ and $a_{i,j}=0$ otherwise. You correctly note that the reversed graph $G'$ will have an adjacency matrix $B=(b_{i,j})$ which is the transpose of $A$, so we'll have $b_{i, j} = a_{j, i}$, since $G'$ will have an edge from vertex $v_i$ to vertex $v_j$ if and only if $G$ has an edge from $v_j$ to $v_i$. To get the transpose of $A$, then, we'll swap $a_{i, j}\leftrightarrow a_{j, i}$ entries of $A$. There will be $n(n-1)/2$ swaps needed, since we swap every element above the main diagonal with its corresponding entry below the main diagonal.

Note that multiplying $A$ by $-1$ won't work, since the entries of an adjacency matrix must be only $1$ or $0$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41053