# Questions tagged [matrices]

For questions about construction and modification of matrices, objects represented by 2-dimensional arrays that are used to define linear operators within linear algebra.

192 questions
Filter by
Sorted by
Tagged with
388 views

### Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
4k views

### Relations and Zero One Matrices

I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices. For example if I have a set A = {1,2,3} and a relation R = {(1,1), (1,2), (2,3)...
10k views

### Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times r$)?
872 views

### Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
166 views

### Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
416 views

### computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
107 views

### Matrix usage in CS [closed]

I'm studying a major in CS. I'm interested in taking a few extra courses, specifically math to improve my knowledge as future computer scientist. Right now I'm thinking to take Matrix Fundamentals ...
Consider the matrix with dimension $m \times m$: $$M = \begin{array}{cc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array}$$ Its 1-D representation: $$M^* = \begin{array}... 1answer 2k views ### Fast algorithm for matrix chain multiplication in special case An exercise from the book Foundations of Algorithms Using Java Pseudocode: Write an efficient algorithm that will find an optimal order for multiplying n matrices A_1 \times A_2 \times \ldots \... 0answers 142 views ### A matrix rank problem over finite fields I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here. Let M|\mathbf w, where M is a matrix and \... 1answer 708 views ### How to use different size features in SVM? I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector. ... 1answer 783 views ### Why linear transformation can improve classification accuracy when the dimensionality of data is high? Let X be an m\times n (m: number of records, and n: number of attributes) dataset. When the number of attributes n is large and the dataset X is noisy, classification gets more ... 0answers 27 views ### Approximation scheme for finding best product of matrices that minimizes ||Ax - y|| for given x,y Given a set of N n \times n matrices A_1,\ldots,A_N, and two vectors x,y, the problem is to find a product of up to K matrices A = A_{j_1}A_{j_2}\cdots A_{j_k} so that Ax is as close to ... 1answer 1k views ### Power method to calculate eigenvectors I've implemented a program for computing eigenvectors of some random, symmetric, NxN matrix using the power method. I have found difficulty in calculating all N eigenvectors consistently, ... 1answer 41 views ### Solving for the matrix W in an equation involving W \cdot W^{T} Having large matrices, W (the unknown) and M (known), is it possible to solve for W in this equation$$W \cdot W^{T} = M,$$where M can have negative entries. 1answer 386 views ### Which computational model is used to analyse the runtime of matrix multiplication algorithms? Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ... 1answer 268 views ### Updating maximum sum subrectangle in a sparse matrix when one element is changed I have an m x n matrix which is sparse with N non-zero entries. A modified version of Kadane's 2-d algorithm can find the maximum sum subrectangle in O(m N log n) time, which beats traditional Kadane'... 1answer 702 views ### How to determine the address of an element in a square matrix given the base address? [closed] I was asked this question in examination. A square matrix M of size 10 \times 10 is stored in memory with each element requiring 4 bytes of storage. If the base address at M is 1840, ... 1answer 101 views ### A canonical representative, for this equivalence relation on matrices This question is inspired by Constructing inequivalent binary matrices. Define the equivalence relation \sim as follows: If M,N are two 8\times 8 binary matrices (all elements are 0 or 1), ... 3answers 8k views ### Number of submatrices with a particular sum Given a n\times n matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ... 1answer 3k views ### Which algorithms are usable for heatmaps and what are their pros and cons This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove ... 1answer 278 views ### Undergrad resources for identifying regular languages with Myhill-Nerode matrices I am taking an undergraduate CS Theory course and the material on finite automata and regular languages is being taught in a non-traditional manner. Instead of using regular expressions, the closure ... 1answer 455 views ### What are some applications of computing the permanent of a matrix? What are some applications that require computing the permanent of a matrix? One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a ... 1answer 177 views ### Count elements of a sorted matrix that fall into a given interval I have a n\times n matrix called M, and two integers k_\min and k_\max. Each row and each column of M is sorted in the increasing order. I would like to know if there is way I can count the ... 0answers 116 views ### Laplace's Approximation for graphical models A question about Laplace's approximation: In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is ... 1answer 381 views ### Significance of parameters in Tiny Mersenne Twister algorithm I am trying to implement and optimize the Tiny Mersenne Twister (TinyMT) algorithm as required by an API I am developing with my team at work. The algorithm utilizes a C structure with 32-bit unsigned ... 1answer 332 views ### Number of permutation cycles in matrix transposition I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/ The matrix can be thought of as a permutation and its transposition as another ... 1answer 1k views ### How to enumerate combinations in parallel I have n\times k matrix with k<n and I would like to find all its n\choose k submatrices which are k\times k matrices that are the concatenations of all possible k rows. Actually I tried ... 1answer 2k views ### Complexity of transposing matrices represented as list of row or column vectors Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix |1, 2, 3| |4, 5, 6| |7, 8, 9| is  \Omega(n^2)  a lower bound for transposing? ... 1answer 1k views ### How do convolution matrices work? How do those matrices work? Do I need to multiple every single pixel? How about the upperleft, upperright, bottomleft and bottomleft pixels where there's no surrounding pixel? And does the matrix work ... 1answer 4k views ### Algorithm for generating heat maps I am looking to generate a heat map from some data. I have a value and a location (longitude and latitude). I understand generating a colour from the value, however I'm not sure how I would go about ... 2answers 891 views ### 2-D peak finding complexity (MIT OCW 6.006) In a recitation video for MIT OCW 6.006 at 43:30, Given an m \times n matrix A with m columns and n rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to ... 1answer 153 views ### LU decomposition with pivoting I have to solve system of linear algebraic equations AX=B, where A is a two-dimensional matrix with all elements of main diagonal equal to zero. How to solve this problem? Iterational methods are ... 1answer 90 views ### How to correlate a matrix of values to get a coordinated point? I got a n*m matrix updated in realtime (i.e. about every 10ms) with values between 0 and 1024, and I want to work out from that matrix a multitouch trackpad behaviour, which is: generate one or more ... 1answer 193 views ### How do you go about designing a vector processor architecture for the sum of matrix products? The following equation is a matrix expression where B_i and C_i^T are n\times n matrices and k is a positive integer:$$P = \sum_{i=1}^k B_i C_i^T  So $P = B_1 C_1^T + B_2 C_2^T + \cdots +... 2answers 3k views ### Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested ... 1answer 201 views ### What's a fast algorithm to decide whether there is an$A_G$corresponding to a given$\chi_G(\lambda)$? Given an adjacency matrix$A_G$of an undirected graph$G$, it is easy and straightforward to compute the characteristic polynomial$\chi_G(\lambda)$. What about the other way around? The problem can ... 2answers 6k views ### Matrix powering in$O(\log n)$time? Is there an algorithm to raise a matrix to the$n$th power in$O(\log n)$time? I have been searching online, but have been unsuccessful thus far. 1answer 3k views ### Using Funk SVD with SGD? I work on a recommender system framework which is implemented with a variant on Funk SVD (See his explanation of his algorithm here). However the framework that we are trying to integrate doesn't ... 2answers 1k views ### Common idea in Karatsuba, Gauss and Strassen multiplication The identities used in multiplication algorithms by Karatsuba (integers) Gauss (complex numbers) Strassen (matrices) seem very closely related. Is there a common abstract framework/generalization? 1answer 500 views ### Probabilistic test of matrix multiplication with one-sided error Given three matrices$A, B,C \in \mathbb{Z}^{n \times n}$we want to test whether$AB \neq C$. Assume that the arithmetic operations$+$and$-$take constant time when applied to numbers from$\...
Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ ...